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!)
May 13, 2022 at 11:52 am
You said this problem was horrendously difficult. Can you think of a bayesian way to quantify the difficulty of a Sudoku problem? Maybe the average number of iterations required to reach the solution?
May 13, 2022 at 12:02 pm
The resolution of said problem by a rather dumb simulated annealing solution is costly, rather than difficult. I am sure Sudoku resolution has been quantified in terms of computational complexity. For instance, it is a NP-complete and ASP-complete problem (Yato, 2003).
February 25, 2017 at 9:33 pm
May you please explian the R code more elaborately? I am having difficulties in understanding it from this.
December 22, 2014 at 1:43 pm
Hi can just explain it more cause I can’t understand the language you have written the program if you can please tell the algorithm complete.
December 22, 2014 at 3:00 pm
I just sent you the R code.
March 17, 2012 at 12:13 am
[…] fantastic book on numerical analysis.) One of these techniques is the simulated annealing approach I had played with a long while ago. They seem to use the same penalisation function as mine, i.e., the number of […]
May 13, 2011 at 12:18 am
[…] first example found in the paper is a sudoku solver, a problem I find quite interesting. The details are missing from the paper, but the likelihood […]
March 1, 2011 at 12:35 pm
[…] I was finishing a sudoku grid in the metro and I ended up with four entries a,b,b,a that could be entered in two symmetric […]
January 30, 2011 at 10:17 pm
[…] this works pretty well for Sudoku (which is NP-hard) as this is brilliantly described here and there. The principle is simple: if one can find a good energy function such that a solution to the […]