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.

Guuurgh

I am pretty much over this whole HTML5 thing. It's just too young to be worthwhile to learn or try to use at this point. Maybe once it's an actual standard I'll come to appreciate the time I put into it, but at this point I'm just frustrated.

At any rate, a while back I actually completed the goddamn music thingy, and even got it working on my browser (firefox 3.5ish). Unfortunately, it doesn't work in safari, and I can't be bothered to figure out why, so there you go.

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.

Spring break is over!

In fact, spring break has been over for two weeks now. And although it may seem like the time was wasted, the two weeks were in fact very productive. None of that productivity, however, had anything to do with the internets, and so I have little to show for it.

To gain back some momentum with this internet thingy, I've put together a super simple list of the things I've done recently, and put them up as their own html pages. Now I ought to get back to making things to populate it. Right after I do some homework.

Gone for a while

I had hoped to get a little more done with the new project before spring break, but seeing as how it was finals week, it's really not surprising that I didn't. And so, spring break is here, and I won't be able to do anything computer-related for around a week or so (thank god). When I get back, though, that <audio> tag will dance for me. I promise.

Hubble Kaleidoscope

Turns out, when a piece of javascript runs very slow and everything I try to speed it up has no real effect, a previously fun project pretty quickly turns tedious. In this case, the culprit was slow drawing code, which in an animation gets called pretty often. Since it's the drawing that's the interesting bit here, there really wasn't much I could do. I decreased the number of calls to drawImage() by making the strips run horizontal instead of vertical, and then decreased the number of transformations the canvas undergoes by once again increasing the number of calls to drawImage(). In the end, I ended up using the drawImage() function to reflect the wedge I copy from the source image. Originally, I had used a scale transform on the canvas to do the reflection, but I suspect it's a bit faster this way.

At any rate, after a long week of tedium and end-of-term homework, the Hubble Kaleidoscope is finished. It runs really quite slow, and does its best to light my computer's processor on fire, so I've decided not to embed it into this blog post. It was getting to be quite tedious to make sure every variable I used had a different name for every blog post anyway. Be wary, javascript will certainly try to kill your computer, and if that doesn't work, it will try to hypnotize you into total obedience.

Here is the actual webpage with the Kaleidoscope on it.
Here is the source code (at pastebin.com).
And here is a neat image to try the damn thing out with.

Next time I have free time, I think I will play around with the <audio> tag, and see if I have any better luck than when I first tried to add sound to the box killer game thing.

Zebras and stars

While thinking about how to best go about copying a triangular section of an image, I've realized just how much easier it would be to do this if the triangle had a couple of sides that are always parallel to the sides of the source image. This would also mean a much simpler algorithm for bouncing the wedge around the source image. On the downside, the bouncing would also be more likely to end up in a loop, where the wedge goes over the same areas of the source image over and over again. This seems like a small price to pay, but who knows, maybe it'll be annoying enough to go need fixing.

So, with everything nice and perpendicular, it seems easy enough to carve a wedge out of an image: just loop through the width of the wedge, copying a progressivly taller and taller 1px-wide strip of the source image. Doing this is much helped by this section of the canvas element's description.

...
triangle = function(kc,img,x,y){
 for(i=0;i<161;i++){
  kc.drawImage(img,       //Source
            x+i,y,        //Pos. in source
            1,(i*0.419),  //Size in source
            i,0,          //Pos. in destination
            1,(i*0.419)); //Size in destination
 }
}

I pass into this function a drawing context, the source image, and the x-y coordinates of where the wedge starts. The factor of 0.419 comes partially from basic trigonometry, to make the wedge have a nice 22.5 degree angle, and partially from experimentation, to make the wedges blend into a circle nicely. As it stands, this function, when called a few times on a translated and rotated canvas, will produce an image that looks like this:

It's pretty clear that while this is along the lines of what I want, it's not quite right. The problems are twofold: the white creases along where two wedges meet, and a striping of the wedges that aren't along the x or y axis.

The striping is caused by the fact that the little strips I am copying end up too skinny when distorted by the rotation of the wedge sections. A very simple solution to this is to simply make the strips wider than one pixel, so that they overlap, and stretching them apart a bit won't let the white-space underneath show through.

The white dot at the center is caused by the simple fact that anything multiplied by zero will be zero, and I start the for loop at zero. This too is easily solved by modifying the call to drawImage() to make the whole wedge shift slightly along the x-axis. This also happens to close up the white rays coming from the middle, in addition to the big hole.

The function, then, becomes this:

...
triangle = function(kc,img,x,y){
 for(i=0;i<161;i++){
  kc.drawImage(img,
            x+i,y,
            2,(i*0.419),
            i-1,0,
            2,(i*0.419));
 }
}

And the result looks more like this:

All that's left is some animation and an interface, but a combination of schoolwork and the time taken to write this post means I'll have to put all that off for a little later. Still, pretty good progress for a couple hours worth of work.