The Omnifarium - Sudoku/26.html

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 #26

Category: Sudoku
Mon, 18 Jul 2005, 06:58

I ran into an interesting conundrum yesterday with one of my Sudoku puzzles. It was solvable by my original Sudoku program written in Python. But my new program written in C couldn't solve it, even though it included a couple of additional advanced solving techniques!

Here's how my old program handled one particular step, as shown by the following diagram. It noticed the three cells in one column with the three possibilities {123}. Since those possibilities must occur in those three cells, these possibilities can be eliminated from the other cells in the group, indicated by the underlining. The program could then apply other techiques and proceed to the solution. (Right away, you can see that the entire middle row can be resolved easily.)

But with the additional advanced methods added to my new program, it applied a different method, as illustrated by the following diagram. With this technique, the intersections of four groups is considered: one column, one 4x4 square in the middle of the board, and two rows. In this case, posssibility 1 must occur in either the upper-left and lower-right indicated cells, or in the lower-left and one of the two upper-right cells. Possibility 1 can therefore be eliminated from the other cells of the two rows, again, indicated by the underlining. (See #16 for further explanation of this technique.)

At this point, my program reached a roadblock, and couldn't proceed without resorting to backtracking. Clearly, the technique used previously no longer applies since we no longer have the three groups with possibilities {123}.

The lesson is that sometimes when you reach an impasse and don't know how to proceed, you have to start over and make different choices along the way to the solution. It's frustrating - you haven't made any mistakes, but still you need to go back to the beginning and try again.

How will I address this in my program? I'm not sure yet. One alternative is to try solving the puzzle again varying the order in which the advanced methods are invoked. But that feels like a kludge solution. There are lots of ways to change the order, which would increase the time needed to solve or generate puzzles. On the other hand, that might be a good way to produce more difficult puzzles!

I still can't shake the feeling, though, that I'm missing some other analytical technique. I need to keep looking for it.

Anyways, in todays puzzle, you can't avoid one particular advanced solving technique. But I'm not telling you which technique it is!

Hans

path: /Sudoku | permanent link to this entry