For Fun: Benchmarking Sudoku Algorithms

[xytroxon]

In the spirit of rickyboy's recent interesting posts on using the problem solving capabilities of the newlisp language, I offer up this "For Fun" challenge, inspired by this old (2011) 'Attractive Chaos' blog that bubbled back up on one of my rss feeds:



'An Incomplete Review of Sudoku Solver Implementations'

http://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/">//http://attractivechaos.wordpress.com/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/

Sudoku is probably the most popular puzzle nowadays. Lots of attempts have been made to solve Sudoku using programs. However, solving Sudoku is known to be an NP-complete problem, which means no efficient algorithm exists so far. Finding the solution largely relies on black magic. On the other hand, lacking a definite answer makes Sudoku more interesting. A variety of methods arise to solve Sudoku. Wiki gives a good brief view of the existing algorithms. I will focus more on the practical implementations.

Searching the newLISP Fan Club found 8 matches for: sudoku

http://newlispfanclub.alh.net/forum/search.php?keywords=sudoku">//http://newlispfanclub.alh.net/forum/search.php?keywords=sudoku



The sudoku.lsp code links from 2005 are now dead. So this would be a good time to revisit the topic, and help benchmark newLISP's speed* against other languages ;o)



One of the unexpected speed demons presented in the article is Lua, while Python and Java methods can be extremely slow, to say the least... (I suspect the Lua version was run using Mike Pall's excellent luajit.)



Sudoku is relatively unknown to me, and I suffer greatly to solve them, (some of our fine newLISP members no doubt can solve these puzzles in their sleep ;o), so this is a challenge to new and old newLISPer's that have a few odd moments to invest.



While this maybe "child's play", the long-term challenge is to use newLISP to evolve the NP-complete problem solving challenge that Sudoku presents...

http://en.wikipedia.org/wiki/Sudoku_algorithms">//http://en.wikipedia.org/wiki/Sudoku_algorithms



-- xytroxon



* And maybe we can break, um... "make more bulletproof" Lutz's newLISP code in the process ;o)