Page 1 of 2 [ 27 posts ]  Go to page 1, 2  Next

Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

26 Oct 2022, 11:05 am

I am forking this topic from another post.

Members Only Discussion > My integral

Fenn wrote:
Complexity and opportunity are closely related. When I was a boy in geometry class I remember reading about something called a "magic square" in a side bar in the text book. Now I like Sudoku puzzles and Sudoku puzzles are a variation on the magic squares I read about in school. Each puzzle has its own complexity and the approaches are not always obvious. The other morning I was working on a variation on a Sudoku puzzle which was 16 by 16 instead of 9 by 9. The options to fill in each cell are 1 thru 16 not 1 thru 9. The diagonal count too - the solved puzzle must have each option only once on both diagonals. The complexity goes up geometrically when increasing the size of the puzzle this way. To solve it using the exact same techniques for a 9 by 9 increase the number of things I need to keep and manipulate in my head in working memory beyond my capabilities (I can only keep 3 or 4 chunks in memory at a time reliably - with efficient chunking I can fake it up to 9 items in groups of 3). The graph paper I use for scratch paper for creating "lemma" guesses cannot fit the whole puzzle on one sheet if I use one square for each possible value for each cell (each cell has at most 16 possible values - and I cannot write small enough to fit 16 tiny one and two digit numbers in each square on the graph paper - if I increase the cell size the puzzle no longer fits on the page). It is an interesting puzzle. I recently came up with a technique of using the paper differently to only try to solve one "big square" (4 cells by 4 cells) at a time reducing the complexity to something closer to the 9 x 9 level of complexity. It reminds me of other problems - computer networks at work, matrices or tensors used for particle physics or matrices and linear algebra. Rubic's Cube and other similar puzzles. Like simple calculus or integral or differential calculus - Sudoku puzzles seem to have to do with "math" because of the numbers on the page, but they really have to do with that other kind of math - symbolic manipulation. I jokingly call this the "Sesame Street School of Mathematics". Like Ernie or Cookie Monster moving letters around the puppet stage. Computers really don't do math, they manipulate symbols - electronic physical states represented as 0 and 1, arranged in patterns to represent integers, which can be used to represent letters and pixels and all kinds of other things. These things can be used as symbols and pairs and arranged in all kinds of cool ways. In complexity is danger - I can spend hours or weeks or even months chasing a rabbit down a metaphorical rabbit hole of complexity and never find "the answer". And doing so can cost me hours and dollars - and have an emotional and physical toll on my body. In complexity there is also opportunity there are places to explore and discoveries to be made and puzzles to solve. This is exactly why I loved maze books as a child, and exploring in the woods behind my house. I can learn about myself and the "exploration space" in the process. I can learn about learning and think about thinking - and I may discover some gem I can keep for a lifetime.

One question is "are you ready" - another question is "do you dare miss this opportunity to explore".

Only you can tell, but I think it might be worth it even if you don't find "the answer" - it might be worth it just for "the explore".


Reply:

Dial1194 wrote:
Fenn wrote:
I cannot write small enough to fit 16 tiny one and two digit numbers in each square on the graph paper


A bit late for a reply, but can you fit sixteen single digits in? There's always hexadecimal notation...


My reply to the reply:

Fenn wrote:
^ I hadn't thought of using hex. I tried copying the puzzle onto a bigger piece of graph paper, but the number of iterations was still higher than I could do in one sitting. I had another idea of only copying part of the puzzle and trying to solve that - including random choices, carefully recorded in a list to allow for "backing out" guesses that later lead to a contradiction. I think the game space is just too big for me and my ADHD brain. I might code it with a computer programming language, but projects like that are the kind of thing I often start and often do not finish. I took a class in artificial intelligence once and wrote a program to solve that 4x4 tile puzzle with one tile missing. It worked. You could put in any puzzle and it would eventually solve it. The way I solve the same puzzle by hand is different than how the program worked. I like these kind of puzzles. I may start another post on this topic so as not to highjack magz's thread.


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

26 Oct 2022, 1:10 pm

Sudoku puzzles:
I came up with a method for solving Sudoku “so hard you MUST make a guess” puzzles that does not require additional paper. (This is for traditional 9x9 Sudoku puzzles).
I find a place in the puzzle where the “right answer” is unknown, but MUST be one of two options. This represents one node in a binary search tree. If guessing one option leads to a contradiction (like in a geometry proof) then the other of the two options MUST be true: for example one of box A1 or box A2 must be “2” but there is not enough information to know which. I start by guessing A1 (where I have marked the puzzle up like a spreadsheet with letters for columns left-to-right and numbers for rows top-to-bottom).
I write the “2” in box A1 and add the notation with one angled line in the top left of box A1 and one angled line bottom right of box A1. If any cell that is now certain based on the clues and previous certain moves I mark this box with the number (for example I now an certian A2 must be “5” if A1 is “2”) i also add the notation for “post guess” by circling the number (A2 is now “5” circled). I continue adding moves with the circled “post guess” notation until I either solve the puzzle, get to an impass, or grt to a contradiction (for example big box with corners at A7 and C9 cannot contain any “8”s at all because of my guess - that is a contradiction - my guess MUST have been wrong). If I get to a contradiction I now erase all circled “post guess” moves, and my guess, replace my guess with the only other of the two alternatives (in my example A2 must be “2” since I now know A1 being “2” leads to a contradiction)

I can extend the method by adding a second guess, again choosing a box that MUST be one of two alternatives (perhaps as a result of guessing A1 is “2” leaves me knowing that either A2 or A3 must be “5”). I add a notation to a second guess of two angled lines in the upper left and lower right (guess A2 is “5” and note this with two diagonal lines upper left and lower right in A2). Post guess-one and post guess-two both get circle notation. A Contradiction leads to erasing all circled post-guess moves and only changing guess-two (Try A3 as “5” if guessing A2 as “5” lead to a contradiction). If both guess-two alternatives lead to contradiction this proves guess-one as false and guess-one’s alternative as true.

I find I can keep up to three guesses in my head using only the notations as described. This solves many puzzles with no extra paper needed. (The third guess’s notation should be obvious).


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

26 Oct 2022, 3:52 pm

Sample puzzle:

Image


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

28 Oct 2022, 8:20 pm

With a little work we get:

Image


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

28 Oct 2022, 8:59 pm

I can make 3 guesses:
B1 = 4 ( not B3 = 4 )
A2 = 8 ( not B2 = 8 )
B3 = 3 ( not C3 = 3 )
This eventually leads to the contraction:
C7 must be 3 and C7 cannot be 3.
(This proves that at least the 3rd guess must be wrong: we want to back up to the 3rd guess and replace it with the alternative: we want to change B3 = 3 to C3 = 3.

Image


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


r00tb33r
Veteran
Veteran

User avatar

Joined: 28 May 2016
Age: 36
Gender: Male
Posts: 3,778

29 Oct 2022, 4:06 am

That looks... Nope.

I play the Killer Sudoku variant on my phone.


_________________
Enjoy the silence.


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

29 Oct 2022, 7:47 pm

... so, I am using a good pencil with a good eraser. I erase all circled (post guess) moves. I erase the third guess (B3 = 3) and add the alternate guess C3 = 3

Image


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

29 Oct 2022, 8:15 pm

Going forward from the new guess I get to a solution. I double check that I didn't make any error in guesses or moves by checking every column, every row and every 3x3 box again after I think I have a solution. In this case I got lucky. Making three guesses where each guess is one of only two possibilities gives me a 1 in 8 chance of being right on the first try. (1 in 2x2x2, like flipping three coins and getting all heads) If I back out guess three and try its alternate I am now sure the first set of guesses was wrong and my odds are a bit better: 1 in 7. Since I know I can back out each guess and replace it with its alternate I also know I can keep guessing all 8 possibilities if I need to, but my odds get better with each guess. Often I don't have to try all 8.

Image

So even with the hardest Sudoku puzzles where I have to guess I don't ever need extra paper.


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

29 Oct 2022, 8:18 pm

r00tb33r wrote:
That looks... Nope.

I play the Killer Sudoku variant on my phone.


You are right, but I wan't quite done.

What is the name of your Sudoku app?


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


r00tb33r
Veteran
Veteran

User avatar

Joined: 28 May 2016
Age: 36
Gender: Male
Posts: 3,778

29 Oct 2022, 10:22 pm

Fenn wrote:
What is the name of your Sudoku app?

Killer Sudoku by Sudoku.com

There might be a better one out there, I just got into it recently, but it's been good so far.


_________________
Enjoy the silence.


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

30 Oct 2022, 8:07 am

Credit for the puzzle I used above goes to

https://www.sudokuoftheday.com/dailypuzzles

(Category: Diabolical)


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


techstepgenr8tion
Veteran
Veteran

User avatar

Joined: 6 Feb 2005
Age: 44
Gender: Male
Posts: 24,150
Location: 28th Path of Tzaddi

01 Nov 2022, 9:21 am

I got curious and started a StackBlitz yesterday evening. I'll see how far I can get on this.


_________________
“Love takes off the masks that we fear we cannot live without and know we cannot live within. I use the word "love" here not merely in the personal sense but as a state of being, or a state of grace - not in the infantile American sense of being made happy but in the tough and universal sense of quest and daring and growth.” - James Baldwin


techstepgenr8tion
Veteran
Veteran

User avatar

Joined: 6 Feb 2005
Age: 44
Gender: Male
Posts: 24,150
Location: 28th Path of Tzaddi

02 Nov 2022, 5:18 pm

What I cobbled together so far for handling easy / beginner but doesn't get off the ground yet for intermediate or advanced:

https://stackblitz.com/edit/create-erer ... mponent.ts

For easy and intermediate I took Wildcat and Diabolical from here:

https://sandiway.arizona.edu/sudoku/examples.html

I'm interested in seeing if there are some puzzles out there on the edge of intermediate which might get stopped maybe a few more moves in or at least enough to give me some additional ideas for how I'd want to automate more heuristics.


_________________
“Love takes off the masks that we fear we cannot live without and know we cannot live within. I use the word "love" here not merely in the personal sense but as a state of being, or a state of grace - not in the infantile American sense of being made happy but in the tough and universal sense of quest and daring and growth.” - James Baldwin


techstepgenr8tion
Veteran
Veteran

User avatar

Joined: 6 Feb 2005
Age: 44
Gender: Male
Posts: 24,150
Location: 28th Path of Tzaddi

07 Nov 2022, 8:05 pm

Keeping on this because work is really slow right now and it's captured my interest for practice and problem-solving reasons. I revamped my code so the base objects that are getting used are easier to deal with (closer to what I'd do with SQL tables - as many data hooks as possible per line).

For logic I added another layer that checks the neighboring (vertical / horizontal) grids against their neighboring grids to see if there are any unset numbers that can be limited to specific rows or columns to then pull those from the primary grid. That approach solved the Medium2 puzzle.

For the one in the OP (I titled it 'WPChallenge') it only needed a couple things:

1) I manually placed the 1 in the second grid top row. That didn't need a guess but it would need something like a third iteration on the logic I mentioned above.

2) Trying the top row in the second grid down on the left (between a 3 and 7) only needed one guess to solve the rest of the puzzle.

The intermediate puzzle still hasn't been dented yet, the new schema only solves two boxes in that one which is no different than before. I'll have to see if I can crack that one a bit farther in the next week or two.

https://stackblitz.com/edit/create-ahfd ... mponent.ts


_________________
“Love takes off the masks that we fear we cannot live without and know we cannot live within. I use the word "love" here not merely in the personal sense but as a state of being, or a state of grace - not in the infantile American sense of being made happy but in the tough and universal sense of quest and daring and growth.” - James Baldwin


Fenn
Veteran
Veteran

User avatar

Joined: 1 Sep 2014
Gender: Male
Posts: 2,404
Location: Pennsylvania

07 Nov 2022, 9:28 pm

I haven't coded it but I read a couple of treatments of sudoku solving in code.
I can do puzzles of all levels by hand - and I do them to destress - I need some time away from a keyboard.
Middle puzzles use a few different tricks. Basic puzzles you can usually do by looking for boxes (3x3) that can (for example) only have 1 in one spot because they are in the shadow of other threes in other boxes.
Middle puzzles you often need to start with the 3x3 boxes and then switch to horizontal and vertical lines.
Another "middle puzzle" trick is when two adjacent boxes have two rows each (the same two rows) leave a shadow on the third box. this can happen vertically and horizontally. The book I have uses a 9 by 9 array for the game, but some of the routines are passed array indexes as if they were pointers, and the lines and rows use the same routines as the 3x3 boxes.
They are just passed different index for each set of 9 boxes. It is kind of cool but a bit hard to read.
There are other tricks like "x-wings" and "chains" which I never use by hand, but I have seen them described on-line.

The other thing I have seen coded is a "create a sudoku". The basic approach is to place numbers as "hints" at random, and run the "solve" code after each number is added. I think it also needs a "contradiction detector" as well. Once you have a completely solved, randomly generated 9x9 grid you then back out moves until you have a sudoku which is solvable, but not solvable in more than one way.

The one I really do want to code is the "Rubic's Cube" type game I have sitting on my shelf - which is actually a platonic solid with each face a regular pentagon. I can do it by hand all but the last face. I need to either work out new moves on paper (lots of paper) or in the computer. I could just find someone else's solution online (the winning moves) but I am stubborn and I want to do it myself.

Once I was on an airplane and I hadn't brought any books or puzzle-books. The magazine provided had three sudoku puzzles and I solved all three and was board. I started creating my own puzzle from scratch. I used the second hand on my watch as a source of random digits, but that was taking too long, then I started picking letters out of the magazine - I created a "decoder ring" and assigned each letter one digit 0 thru 9. Three random digits gave me a x and y position and value to place. I kept track of all moves so I could back out if I got to a contradiction. I was eventually able to solve my own randomly generated puzzle using regular sudoku moves and double checked that the final solution had each row, column, and 3x3 box with one each of all 9 digits. It was fun. I don't know if my puzzle had more than one solution at some point in the middle, but the result was satisfying to me.


_________________
ADHD-I(diagnosed) ASD-HF(diagnosed)
RDOS scores - Aspie score 131/200 - neurotypical score 69/200 - very likely Aspie


wbport
Sea Gull
Sea Gull

User avatar

Joined: 16 Sep 2012
Gender: Male
Posts: 220

13 Nov 2022, 11:09 pm

This is the Roche solver I tweaked a few years ago: RocheSudoku
I had to add a guess of 7 in the lower left corner for it to work.