Sudoku solving

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.

Funny buttons

Over the last few weeks I've been working, rather sporadically, on something that I thought would be a neat, easy and fun way to get me fiddling with the <audio> HTML5 tag. A sort of tone matrix clone with a bit of a twist.

In the implementation linked above, a user clicks on squares to toggle them on and off. At regular intervals, the script looks at the next column within the grid and plays whatever tones are associated with each of the squares currently marked as being on. By making a pattern, the user specified a melody to be played.

I thought it would be neat if the pattern a user inputs into the grid could be further manipulated. Specifically, I wanted to be able to rotate and translate the pattern. This shouldn't really be very hard.

Indeed, the math you need to move some points around is not very complicated. I even thought about throwing in the ability to scale the pattern, but figured that wasn't as interesting. The hard part was making controls for these transformations.

Since one of the cooler points of HTML5 is its ability to run on certain mobile devices, I thought that it was pretty important that the controls be such that a keyboard is not required. The obvious way to do so is to make a bunch of clickable buttons, each of which controls some particular transformation direction. So, in order to move the pattern in two dimensions and rotate it both directions, I would need six buttons. At that point, they'd have to be quite small to fit in the canvas, and it would probably fairly difficult to click a particular one using a finger. I thought I could do better.

A pretty natural angular control scheme, which a lot of sounds systems out there already use, is a dial wheel. This eliminates two of the buttons, which means it can be bigger, and therefore easier to control. Similarly, instead of glorified on-screen arrow keys, I chose to make a sort of joystick. I believe each of these is more natural to use with a finger than an on-screen keyboard equivalent. Since I do not have an iPad, or an iPhone, or any sort of touch-screen mobile device, I haven't been able to properly test this way of controlling things with a touch screen, but sticking my finger on the screen and making "whoosh" sounds as I rub it around makes me think it should be pretty intuitive and convenient.

Here, then, is a screenshot that is also a link that takes you to a page where you can play around with the controls.

Unfortunately, the difficulties of implementing this control scheme, which are mostly to do with atan(x) being a double-valued function and me being an idiot, I haven't yet gotten to the part that makes this whole idea cool or useful: the audio. Sometime soon, however, I hope to get some sweet tunes out of this thing.