Sudoku and related puzzles

Post Reply New Topic

I am forking this topic from another post.

● Members Only Discussion > My integral

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).

Sample puzzle:

With a little work we get:

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.

That looks... Nope.

I play the Killer Sudoku variant on my phone.

... 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

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.



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

Credit for the puzzle I used above goes to

https://www.sudokuoftheday.com/dailypuzzles

(Category: Diabolical)

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

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.

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

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.

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.