The Omnifarium - Sudoku

Notice

I am no longer posting new puzzles to this blog. For all of my Sudoku puzzles, old and new, please visit Sudoku in another section of this website. I will still create and offer new puzzles, in batches of a couple of hundred, once a week or so.

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