Solving Sudoku with Simulated Annealing

February 25, 2010
By

(This article was first published on Revolutions, and kindly contributed to R-bloggers)

How long would it take you to solve this devlishly hard Sudoku puzzle (from Le Monde)?

Sudoku 

You could do it the old-fashioned way -- with a pencil -- but Xi'an decided to solve it by programming a simulated annealing solver in R. The algorithm works by first guessing a solution at random -- filling in the empty cells above with random digits between 1 and 9. Then it "scores" this solution by counting the number of digits duplicated in all the rows, columns and blocks. Next it evaluates a number of candidate new solutions by tweaking one of the free digits, and scores those. The algorithm then selects one of the candidate solutions at random for the next step, weighted by the change in the score.

The code to do all this , which you can use to solve your own Soduku puzzles if, say, you've lost your pencil, is at Xi'an's blog.

Xi'an's og: Sudoku via simulated annealing

To leave a comment for the author, please follow the link and comment on his blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags:

Comments are closed.