aaron evans

I was waiting in the airport and decided to buy a Sudoku book. I knew the game and thought it would be a nice way to pass some time. I bought the book with The Times logo on it.

We only had a pen with us and I knew that people typically used pencils because people like to make try values and backtrack if they’re wrong. I decided I could use a pen.

The book arranges puzzles into difficulties of easy, mild, difficult, and fiendish. The easy games are somewhat mindless and I didn’t regret the use of a pen. I only needed an eraser when I hit difficult. I never finished a difficult puzzle because I didn’t like the idea of guessing the value of a square and seeing what happened and then backtracking if I was wrong. This was my first clue that a general solution to the problem may not be trivial.

So, when I returned home I decided to write a little Sudoku solver in Java. I didn’t try to see if simple solutions were available on the web or what the complexity of the problem was; i just tried to solve it. The techniques I used were simply the same techniques I used to manually solve the puzzle which are generally known as Candidate Elimination. I used dynamic programming to speed things up and the solutions that were generated were generated instantly. The solver could solve the easy, mild, and difficult puzzles I fed to it. However, I could not solve all puzzles and at this time and I started to contemplate using a backtracking technique to solve puzzles (guess a value, see what happens, retry on failure).

I couldn’t bring myself to write such code because I knew that such a scheme would likely make the algorithm superpolynomial and I have no interest in writing such algorithms and hate the thought of doing so if some polynomial solution exists. I didn’t feel like trying to prove the problem NPC when Google is oh so close. Faced with this reality, I googled Sudoku and was greeted with the good news that, in the general case (nxn board), Sudoku is NP-Complete. Whew! I would have felt stupid if there was some clever dynamic programming algorithm to solve the problem.

So, with that news, I’ve ended my effort in writing a Sudoku solver because the mystery of an elegant solution has faded.

This entry was posted on Friday, September 15th, 2006 at 4:17 pm and is filed under Development, Me. You can follow any responses to this entry through the RSS 2.0 feed. Responses are currently closed, but you can trackback from your own site.