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

### One Response to “sudoku break”

1. […] a long lag (due to my missing the free copies distributed at Paris-Dauphine!), here is a Sudoku-like Le Monde mathematical […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.