Xi'an's Og

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..!

This entry was posted on December 13, 2013 at 12:13 am and is filed under pictures, R, Statistics with tags Liberation, SAMSI, simulated annealing, sudoku, Warwick. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.