Over the last week or so, I've thrown together a simple sudoku solver. Despite my growing dislike for the HTML5 fad, the javascript and canvas tag combination is apparently still my best friend, as it still takes almost zero time between typing in a few lines of code and checking it out in a browser. As always, I have no proof or guarantee that this'll work for anyone using a browser different from my own (safari 4.0.5 in this case), but I suspect that without the extra bulk of the audio tag, things should go according to plan for everyone.
Solving a sudoku is a fun pastime for many people, me included. It's a nice way to get the brain going in the mornings, and a good way to make sure the part of your brain responsible for logic hasn't failed you yet. This is because solving a sudoku is a very algorithmic process. Something that is not conceptually difficult, but takes attention and care to pull off successfully.
As a mere mortal, every so often (more often than I care to describe) the attention it takes to solve a sudoku is more than I can handle. Fortunately for me, computers are much better at keeping track of what they do. And, since sudoku solving is easily described as an algorithm, computers can be told what they need to keep track of to solve a given sudoku pretty easily.
The steps anyone needs to take to solve a sudoku are fairly simple:
1: Start with an array of 81 squares.
2: Using the starting puzzle as a guide, fill in those squares that are already given as a number by "setting" those squares.
3: Walk through the array of squares, considering each square. If a square has only one number it could possibly be, "set" that square to that number and skip to 4. If a square doesn't have any numbers it could possibly be, give up, because there is no solution possible.
4: If a square was set to a number in 3, jump back to 3. If no square was set to a number in 3, find a square with the fewest possibilities left and move on to 5, unless all of the squares are already set, in which case, we're done.
5: Make a copy of the current array, then in the actual array, set the square from 4 to any value possible for that square. Proceed back to 3, but if 3 gives up because no solution is possible, revert to the stored copy of the array. Then, remove the number that was used from the possible numbers of the square that was set and go back to 3.
Of course, as always, the magic is in the details. Specifically, the details of how setting a number works. As per the rules of sudokus, each column of a 9x9 square must have the numbers 1 through 9, as must each row, and so must each of the nine 3x3 squares that makes up the larger 9x9 square. This suggests that when I set a square to a number, I must eliminate that number from the lists of possible numbers that the affected squares could take on. This, combined with the above procedure, is enough to solve any sudoku, it what appears to be good time.
Implementing this is not really a challenge, but I though I'd go ahead and throw in a convenient way to input the puzzles. That, in turn, turned out to be a bit of a pain. Nonetheless, I have done all that, including what I thought was a rather neat radial menu the concept for which I "borrowed" from some blogpost I'd read a few months ago. Towards the end I got awfully lazy, and rather than bothering to start up GIMP or something to make neat images for the "Solve" and "Reset" buttons I just threw in two more canvases and called them buttons. Still, they don't look too bad, and work well enough.
