Saturday, December 08, 2012

Setting up a general Sudoku solution

kw: puzzles, analysis

I have been addicted to solving the daily Sudoku puzzle since I first saw them a few years ago. I've gradually learned a number of strategies, so that I can usually "do" the ones with up to three stars of "difficulty" with minimal writing. Sometimes I can solve a 4-star puzzle without writing much, but today I saw that there were no easy hits, so I set up the General Solution method that I can use to solve almost any Sudoku.

As you can see in this first image, it involves writing in each empty square all the numbers that it could possibly contain, in a pattern that makes recognition easy. In this puzzle with 24 clues, there are actually three "low hanging fruit" that the setup reveals, which the three arrows point out. I cannot yet "see" such solution squares without writing the setup. Now look in particular at the top center block. The arrow points inside to a lone 6. Once I erase the little 6 and write it in full size, I erase all the 6's in that block, row and column. Now you can see that the 5 at the top is by itself, so it is the next square solved. Then the one below that will have only an 8, and that one is also solved.

The other two arrows point to 1's. "Doing" them and erasing all 1's that they eliminate, we'll find some more singletons. At the very least, to the right of the 5 at the center of the third row up, the 7 will be next.

Here is the puzzle about half done. Getting this far was easy. We are still in a realm of one-solution-leads-to-another. The two arrows show a 3 and a 9 that are next, and it is easy to see that a 4 will be found next to the 3, and a 1 just below the 9. In addition, the squares in that same row are both solved: a 5 on the left and a 2 in the middle. The 5 is also a case of only-one-in-the-row. You need to be on the lookout for such items.

We are starting to see "completion groups" show up, such as the two squares with only 3 and 7, at the lower left. I notice that I haven't yet erased a 1 below a 4 and 3 at top center; that leaves a 9...nor a 3 in the bottom square (that I should not have written in the first place!), so that block is solved already.

Then look at the top center block. The three unsolved squares contain 1 2, 2 9 and 1 9. This is a "completion group" of three squares. If any square is "picked off" by a solution elsewhere, all three are solved immediately.

Here we are near end stage, and the going gets a little harder. No more lone numbers appear, but with a little checking, we can see that the two circled 1's are next (they are both next to the central block). Firstly, the 1 at the left is the only one in that block. Then, the 1 on the right will be the only one in its block.

The upper row with a circled 1 will then have a 7 near the right end to solve next. Also the block to left center has an 8 only in its center square, so that is solved. And so forth.
Here is the solved puzzle. Although I made a couple mistakes during setup, they were easily caught. That is not always so, and I sometimes find I've misled myself. Once I catch a contradiction, I just mark the puzzle "not solved" and wait for the next day's version. I am not going to go back and erase everything and start over!

Something I see in some 5-star puzzles is the pathological situation where you wind up with five or six (or maybe more) completion groups, and none appears solvable. What I do in such a case is study the puzzle to find where I can make a fruitful guess. I'll lightly draw a square around my guess, then circle (lightly) the solutions to which it leads. Sometimes this solves the whole rest of the puzzle. Half the time, it won't, and will lead to a contradiction. But I have a record of my chain of logic. One thing I know is, my initial guess was wrong. I erase that number, carefully erase the light circles, and make a different guess. Because I nearly always make my first guess as one of two, that other "guess" is actually a certain solution of that square, and the solutions to which it leads will usually solve the rest of the puzzle. I have only seen one case in which a chain of logic "dried up", and I had to make a second guess.

If you've never tried such a general solution, and just tend to space off tougher puzzles, give this method a try.

No comments: