- Easy
- A Bit Harder
- Tricky
- Even More Tricky
- Hmm, Can't do this one
Sudoku
Recently, the Sudoku puzzle has become very popular in Australia (or at least in the Sydney Morning Herald - I can't vouch for other papers). In essence, the game is very simple - a nine-by-nine grid contains the numbers one to nine with the following rules:
- Each digit must occur exactly nine times
- Each row must contain one and only one of each digit
- Each column must contain one and only one of each digit
- Each block of nine squares must contain one and only one of each digit
Typically, you are given 28-30 of the numbers and you have to deduce the rest. To be "proper" Sudoku, the pattern of these givens should be symmetrical and there should be only one valid solution.
Interestingly, although the name is Japanese the game is not, although I gather it is extremely popular in Japan. For a good history of the game visit the Wikipedia.
Computer solutions
The game has also become a popular computer exercise. Most of these solutions involve recursive testing of numbers, backing out when a rule is broken. By general agreement the most elegant of these solutions is by a certain Donald Knuth (anyone surprised by this may turn in their Computer Nerd badge right now) with the so-called Dancing Links Algorithm. I wish I understood it.
Even without my incompetence in this area, I find these solutions uninteresting from an AI point of view. I acknowledge that the incompetence may be the cause of the lack of interest. Howsoever, I was/am more interested in producing a solution which thinks more like a human would.
Javascript Solution
To this end, I decided to see if I could write a Sudoku solver in javascript - mainly for the convenience of being able to run it in a web page. It's not the most efficient, or indeed easiest, language for the problem (he said stating the obvious) but it is convenient. I may re-write it in C one day. Or Lisp if I ever learn Lisp. (Who was it who said that expanding the radius of knowledge merely increases the circumference of ignorance? I feel my ignorance expanding every day.)
Angus Johnson has written a nifty description of techniques to solve Sudoku, which I decided to try and implement in Javascript. He has also written a very nice interface to enable you to play the game online which may be of interest. He identifies the following:
- Singles: for any given row, number or block there is only one position in which a given number can go.
- Doubles: where a pair of numbers is in two boxes, they cannot be in any other in that group. In the specific case of only three blanks within a group, the third box must contain the third number.
- Triples and Quads: like Doubles only more so.
- Special Patterns: X-Wing, Swordfish, Gerbil*
To these you can add comparing two blocks and looking for interecting row/column within the block for a given number.
Anyway, it more or less works. It doesn't yet support Triples, Quads or Special patterns. I have one example which doesn't work (see above). If you find any others please let me know.
I'll update the script to work properly when I have the time. Honest.
* OK. I made up Gerbil.