Wednesday, October 05, 2005

Sudoku

Sudoku seems to be the latest craze. I first came across it when we flew to the States at the end of July; the stewardesses handed out a book of puzzles to everyone and most people knew what to do with it. I successfully ignored this craze until a few days ago when my wife came home with a book and started trying to complete the puzzles. Being the sort of person that I am, I knew that I wasn't interested in solving one specific puzzle; no, I would prefer to develop an algorithm and then write a computer program to solve the puzzles.

 It was clear that the algorithm needed to do backtracking; such algorithms are much clearer in the Prolog language than any other. I started working on a program, but then thought that I ought to see what's on the net; instead of inventing the wheel, I can use other people's solutions. Googling for 'sudoku prolog' brought up this link, and 'sudoku delphi' gave me this article; unfortunately the code was for Delphi.Net and what appears to be a console application, but it wasn't difficult to turn it into a Delphi 7 app which uses a string grid to display the Sudoku puzzle. I tried this app with the first puzzle in my wife's book, and almost instantaneously appeared the solution on the screen (and my computer's cpu runs at 866 MHz, so it's hardly the fastest in existence). I checked in the book, and yes, it was the same solution. 

Then I tried the program with one of the advanced puzzles; the difference between simple and advanced is the amount of numbers already present in the puzzle, with the simpler puzzles having more numbers. Again, the program solved the puzzle in an instant, but the solution presented was not the same as the one in the book, even though it appeared to be valid. There's no reason why there can't be more than one solution to a puzzle, especially if there are more degrees of freedom (ie fewer numbers at the beginning). I imagine that someone somewhere has written a doctorate on the subject, so I'm not even going to guess. I can't really see the point of sudoku. As usual, the wiki contains plenty to read on the subject.

No comments: