Site icon R-bloggers

Sudoku via simulated annealing

[This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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


Filed under: R, Statistics Tagged: simulated annealing, sudoku

To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.