Sudoku via simulated annealing
The Sudoku puzzle in this Sunday edition of Le Monde was horrendously difficult, so after spending one hour with only 4 entries filled, I decided to feed it to the simulated annealing R program I wrote while visiting SAMSI last year. The R program reached the exact (and only) solution in about 6000 iterations, as shown (?) on the graph above. The Sudoku grid is defined in the R program by a 9×9 matrix s and the simulated annealing target function counts the number of duplicates
target=function(s){
tar=sum(apply(s,1,duplicated)+apply(s,2,duplicated))
for (r in 1:9){
bloa=(1:3)+3*(r-1)%%3
blob=(1:3)+3*trunc((r-1)/3)
tar=tar+sum(duplicated(as.vector(s[bloa,blob])))
}
return(tar)
}
After pruning out the deterministic entries (3 in my case!), the R program uses the temperature sequence
lmax=10^5#/target(matrix(sample(1:9,81,rep=T),ncol=9))
temps=exp(sqrt(seq(1,log(lmax)^2,le=Niter+1)))
to weight the target function. and it runs over the 10,000 iterations random moves on some of the unallocated sites. On the graph above, the green dots correspond to accepted moves. The yellow dots correspond to accepted proposals to move a single site. These choices lead to a correct solution most of the time, the other cases most often producing a penalty of two. (Please note there is nothing optimised about my code. It takes ten to twenty minutes to produce the graph above. a far cry from the fastest Sudoku solvers!)
January 2, 2011 at 12:10 am
[…] the first issue of Le Monde magazine, including the solution to puzzle #52 I solved just in time by simulated annealing! The trick is in using the following theorem: Iter(1,x,y) is divisible by 10x-1 if and only if y is […]
December 31, 2010 at 8:54 am
[…] completely at rest!). However, this sounds like the last resort solution and I thus tried first a simulated annealing approach already tested for the sudoku problem a few years ago… (This puzzle is actually of […]
June 6, 2010 at 2:44 pm
[…] annealing” methods have succesfully been used to solve the Sudoku problem though: see Christian Robert blog for example. I am also planning to continue my reading of the fascinating book […]
May 16, 2010 at 11:11 pm
Interesting approach to solve a sudoku puzzle using simulated annealing. I have not seen that before. Very good.
However, every sudoku can be described as an instance of the exact cover problem. This allows both for a very elegant description of the problem and an efficient solution using a backtracking algorithm called the Dancing Links algorithm, also known as DLX suggested by Donald Knuth. This Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the N queens problem, and Sudoku.
I use this method in my Sudoku Instructions program, which can solve every sudoku instantly.
However, the Sudoku Instructions program can also be your helpful assistant during solving of the puzzle by providing hints, tips and comments at every step.
Best Regards.
Erik Christensen
May 17, 2010 at 8:10 am
Erik: Thank you for the pointer. Again, the sudoku solver has no claim to efficiency, it is a simple illustration of simulated annealing for my R course…
April 19, 2010 at 12:45 am
[…] more random than random! Darren Wraith pointed out this column about sudokus to me. It analyses the paper by Newton and De Salvo published in the Proceedings of the Royal […]
March 5, 2010 at 10:42 am
Neat! (And slow :-) )
There is a ‘}’ missing at the end of the program code.
March 1, 2010 at 11:25 am
..pretty good idea.
February 27, 2010 at 4:28 pm
[…] kirjutas üks R-bloggeri aktiivsemaid postitajaid Xian [3] , kuidas ta lahendas simuleeritud karastamise algoritmi […]
February 26, 2010 at 12:07 am
[…] here is the Sudoku that started my blog on simulated annealing, nicely represented on Revolutions. (Although I cannot see why the central […]
February 23, 2010 at 8:01 am
Can you please post your Simulated Annealing code.
February 23, 2010 at 8:14 am
Ok, I put link to my (very basic) code.