# sudoku break

December 12, 2013
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

While in Warwick last week, one evening after having exhausted my laptop battery, I tried the following Sudoku (from Libération):

>   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 |
+-------+-------+-------+


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

  +-------+-------+-------+
| 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 |
+-------+-------+-------+


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

Filed under: pictures, R, Statistics Tagged: Liberation, SAMSI, simulated annealing, sudoku, Warwick

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...