#12 Limited solution algorithms

[Andrew Barnert]

pythonsudoku-0.12.4 handle only the three simplest solution algorithms, and even these without full generality. This means that it can neither solve nor generate hard problems.

As is, it can't even solve all of the puzzles at websudoku.com; at brainbashers.com, it can solve only some of the puzzles at hard level, and almost none beyond.

However, if the site is going to say, "If you found a valid sudoku (a sudoku with only one solution) that Python Sudoku can't solve, please, send a bug report with the sudoku (preferable in sdk format) and the method needed to be solved," it should handle most of the popular methods.

Rather than come up with an example puzzle for each method that's missing (although I'll give one below), let me just refer you to http://brainbashers.com/sudokuhelp.asp, which has details on the methods their site uses, as well as a plain list of additional algorithms that were left out because they're not human-appropriate. Of course their choices are arguable, but it's a good start.

That site can also generate a "super hard" puzzle requiring any chosen method. (It's not always perfect; the puzzle may be solvable with a combination of different methods. But you can just keep generating them until you get one that can't be solved with the algorithms currently coded.

One more word about brainbashers: They do a good job describing the methods, giving you puzzles to test them against (with step-by-step solutions), and offering a decent interface with nice hinting. However, they sometimes use some very odd terminology, and some of their descriptions aren't really exact enough to code from. So you'll still need to look at Wikipedia or elsewhere to fill in the gaps.

Here's a "very hard" example from brainbashers that pysdk can't solve.

0 5 0 7 0 9 0 1 0
6 0 0 5 4 1 0 0 8
0 0 0 0 2 0 0 0 0
5 7 0 0 0 0 0 2 3
0 4 2 0 0 0 5 8 0
9 8 0 0 0 0 0 7 4
0 6 0 0 5 0 0 0 0
8 0 0 4 9 3 0 6 5
0 9 0 6 0 2 0 4 0

Even after giving it a few more numbers (which eliminates the need for one algorithm), it fails:

0 5 0 7 0 9 0 1 0
6 0 0 5 4 1 0 0 8
0 0 0 0 2 0 0 5 0
5 7 0 0 0 4 0 2 3
0 4 2 0 0 0 5 8 0
9 8 0 2 0 5 0 7 4
0 6 0 0 5 0 0 0 0
8 0 0 4 9 3 0 6 5
0 9 5 6 0 2 0 4 0

Here's the solution:

2 5 8 7 3 9 4 1 6
6 3 7 5 4 1 2 9 8
4 1 9 8 2 6 3 5 7
5 7 6 9 8 4 1 2 3
1 4 2 3 6 7 5 8 9
9 8 3 2 1 5 6 7 4
7 6 4 1 5 8 9 3 2
8 2 1 4 9 3 7 6 5
3 9 5 6 7 2 8 4 1