sudoku break
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..!
March 27, 2017 at 6:00 am
[…] a long lag (due to my missing the free copies distributed at Paris-Dauphine!), here is a Sudoku-like Le Monde mathematical […]