While in Warwick last week, one evening after having exhausted my laptop battery, I tried the following Sudoku (from Libération):
[sourcecode language=”r” gutter=”false”]
> printSudoku(readSudoku("libe.dk"))
+——-+——-+——-+
| 4 6 | 2 | 3 9 |
| 3 | | 2 |
| 7 2 | | 5 6 |
+——-+——-+——-+
| | 9 4 5 | |
| 5 | 7 6 2 | 1 |
| | 3 1 8 | |
+——-+——-+——-+
| 6 9 | | 1 3 |
| 7 | | 9 |
| 3 1 | 9 | 4 7 |
+——-+——-+——-+
[/sourcecode]
and could not even start. As it happened, this was a setting with no deterministic move, i.e. all free/empty entries had multiple possible values. So after trying for a while and following trees to no obvious contradiction (!) I decided to give up and on the next day (with power) to call my “old” sudoku solver (built while at SAMSI), using simulated annealing and got the result after a few thousand iterations. The detail of the exploration is represented above, the two colours being code for two different moves on the Sudoku table. Leading to the solution
[sourcecode language=”r” gutter=”false”]
+——-+——-+——-+
| 4 8 6 | 5 2 1 | 3 7 9 |
| 1 3 5 | 6 7 9 | 8 2 4 |
| 7 9 2 | 8 3 4 | 5 1 6 |
+——-+——-+——-+
| 2 1 3 | 9 4 5 | 7 6 8 |
| 5 4 8 | 7 6 2 | 9 3 1 |
| 9 6 7 | 3 1 8 | 2 4 5 |
+——-+——-+——-+
| 6 2 9 | 4 8 7 | 1 5 3 |
| 8 7 4 | 1 5 3 | 6 9 2 |
| 3 5 1 | 2 9 6 | 4 8 7 |
+——-+——-+——-+
[/sourcecode]
I then tried a variant with more proposals (hence more colours) at each iteration, which ended up being stuck at a penalty of 4 (instead of 0) in the final thousand iterations. Although this is a one occurrence experiment, I find it interesting that having move proposals may get the algorithm stuck faster in a local minimum. Nothing very deep there, of course..!
