<p><pre><code> Why did I do this? As computer security expert Ben Laurie
has stated, Sudoku is "a denial of service attack on human
intellect". My wife was infected by the virus, and I wanted
to convince her that the problem had been solved and didn't
need any more of her time.
</code></pre>
Very true.
I remember doing something very similar in college. My first cut used a hideous object model, but my second go at it used a 3 dimensional matrix to track all of the data and was much faster and space efficient.<p>The "Why?" at the end of the article pretty much sums up why I can't play most board games and puzzles. Once you 'solve' sudoku, chess, connect 6, ect. it really takes the fun out of it, even if your brain doesn't calculate the solution as quick as your code.
Norvig tries to test his program against the hardest puzzle he can find, but only tries to find this hard puzzle by generating random ones. The program Sudoku Susser (<a href="http://www.madoverlord.com/projects/sudoku.t" rel="nofollow">http://www.madoverlord.com/projects/sudoku.t</a>) actually comes with “the hardest sudoku in the world”, which I think the author of that program has proven somehow, so Norvig should try his program on that.<p>Sudoku Susser can solve sudoku puzzles not only the brute-force way shown in the article, but also using “human” reasoning, and show you all the steps.
He could have used Mechanical Turk to solve them. ;)<p>Growing up, we had a favorite game. That is until my sister solved it in that going first you could <i>always</i> win. It wasn't as fun after that.
Would be interesting to see how this fares performance-wise in comparison:<p><a href="http://corp.galois.com/blog/2009/3/18/solving-sudoku-using-cryptol.html" rel="nofollow">http://corp.galois.com/blog/2009/3/18/solving-sudoku-using-c...</a><p>It's a sudoku solver based on Cryptol, which is "... a language tailored for cryptographic algorithms." built on top of Haskell. The amazing this is that all you need to define is a function that checks whether a given board is solved. Cryptol does the searching for you!
I find that calculating the sequence of stereo pairs for an MP3 file is much simpler and more accurate if I dispense with the human listener.<p>For instance, I just rendered "In the Year 2525" 593 times faster than a human can listen to it on a single thread of a core i3.
Reminds me of:<p><a href="http://blog.jgc.org/2010/01/more-fun-with-toys-ikea-lillabo-train.html" rel="nofollow">http://blog.jgc.org/2010/01/more-fun-with-toys-ikea-lillabo-...</a>
If you really want speed, then I would recommend using a good implementation of Dancing Links for solving constraint satisfaction problems. Don Knuth proposes a doubly linked list structure to speed up recursive state space exploration: www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz.
I wrote one in JavaScript a long time ago, again using a simple backtracking algorithm.<p><a href="http://www.amrittuladhar.com/projects/sudokusolver/" rel="nofollow">http://www.amrittuladhar.com/projects/sudokusolver/</a><p>EDIT: Just realized the "load puzzle" feature doesn't seem to work on Chrome, but it does in other browsers.
I wrote one in C# a while ago:<p><a href="http://isaksky.wordpress.com/2010/10/30/objected-oriented-solution-to-every-sudoku-puzzle-in-csharp/" rel="nofollow">http://isaksky.wordpress.com/2010/10/30/objected-oriented-so...</a>