The Omnifarium

Sudoku #60

Category: Sudoku
Sun, 21 May 2006, 19:51

In my last Sudoku weblog posting, I described another solving technique I recently stumbled upon. Of course, I added the technique to my program. I was initially quite pleased to see my program generate lots of puzzles that needed to use this technique. However, additional analysis turned up something. Many of the generated puzzles had the undesirable property of having multiple solutions.

To begin with, here's a quick summary of the new method: Look at the four cells at the intersection of two rows and two columns. If three of the cells have possibilities {ab} and the fourth has possibilities {abc}, the fourth cell must be c. Otherwise, the puzzle would have multiple solutions.

The following is a fragment of what can be produced when the technique is applied to a randomly generated board:

In this case, there are two possible solutions:

Why does this happen? This solving technique works so long as we know there is only one solution. Unfortunately, while we are still generating a puzzle, we can't yet be sure that we have a unique, solvable puzzle.

Does this mean one can't reliably generate a puzzle that uses this technique? No. It just means that some additional checking is needed to ensure that you end up with a puzzle with a unique solution. At least, you can use brute-force back-tracking analysis to try to generate all possible solutions. I suspect that may be overkill, though.

Or at least, I hope that brute-force back-tracking is overkill. I tried to weed out invalid puzzles by repeating the new technique backwards to see if the same solution comes out. But while this can find some cases of invalid puzzles, it can still let through other invalid puzzles.

The bottom line is that more work is needed before I can post puzzles that need this new technique.

Hans

path: /Sudoku | permanent link to this entry

Sudoku #59

Category: Sudoku
Sun, 07 May 2006, 17:09

After doing Sudoku puzzles for about a year, you might think there's nothing left to learn about the puzzle. On the contrary, I never believed for a moment that I knew all there is to know about Sudoku. Actually, I always suspected that there was yet another solving technique to be discovered. And finally, this past week, I came across that technique.

Here's part of my solution and notes to puzzles S72.60 in the Standard Puzzles:

Note that the cells marked with yellow have the possibilities {14}. But the cell to note is the cell marked in blue with possibilities {149}. Let's assume that the blue cell does not have the value 9. All the yellow and blue cells would then have the possibilities {14}. This would mean that the puzzle would have two solutions! Since valid Sudoku puzzles must have unique solutions, our original assumption must be wrong, and the blue cell must have the value 9.

The following diagram illustrates the technique:

Consider the four cells at the intersection of two rows and two columns. If three of the cells have possibilities {ab} and the fourth has {abc}, then possibilities {ab} can be eliminated from the fourth cell. Note that c might be one or more possibilities.

Also note that, unlike the other advanced techniques described in How to Solve Sudoku, this one can result in the direct determination of the value of a cell.

Anyways, what does this new technique mean to my puzzles? Clearly, none of my 150,000 puzzles require this technique. I said I wasn't going to post any more new puzzles. But I may have to reconsider that decision. I'll add this new technique to my program, and then I'll see if it's possible to generate puzzles that do require this technique. If so, then I may have to add some more puzzles.

Hans

path: /Sudoku | permanent link to this entry