Knight’s Tour Problem

A knight's tour

One of the homework problems we had in graph theory class asks the question: given a Knight piece and an 8×8 chessboard, can you start the Knight off on one square, move into every other square once and exactly once, and land back on the square that you started with? This is a really annoying problem because it’s easy to understand and sucks you in for hours. I only got half credit on it by trying to fill a 4×4 part of the board as much as I could and copying the same moves 4 times.  Apparently, a Knight’s tour doesn’t exist for a 4×4 as Professor So mentions some theorems about this problem. If you’re interested in more, check out Schwenk’s theorem.

Coincidentally, I was randomly practicing programming problems in Topcoder and I found that the Knight’s Tour makes an appearance as the 2nd problem in division 2, SRM 447. The problem has you implement an algorithm, namely Warnsdorff’s algorithm, which is a heuristic algorithm that makes the Knight piece walk the board, and if you start with a fresh board with the Knight in a corner, you can actually discover a Knight’s tour. BUT, the thing is, it doesn’t give you the elusive Hamiltonian circuit but rather a Hamiltonian path ie. the starting and ending points that you find with this algorithm are different. Still, it’s pretty awesome for a 500 point problem.

The cool thing about that algorithm is that although the Hamiltonian path problem is NP-hard, it supposedly is able to find Hamiltonian paths in many graphs in linear time. I’ve attached my Java program if you just want to test it out. Don’t worry about having seen this tour and having the problem being spoiled; apparently, there are billions of possible tours. Also, I have not found the Hamiltonian circuit yet, so good job if you managed to find it but don’t tell me 🙂

KnightsTour.java

Matrix pivoting in Javascript

I know, it’s a ridiculous idea to write up a scientific computing algorithm that has cubic complexity and is heavy in floating point operations in Javascript, and making it use a randomized function to select the pivot element guarantees that it is completely useless. But it’s got buttons and it’s kinda fun to look at: http://tinyurl.com/gerp143m

Animation is kind of strange to pull off. Scriptaculous has these things called effect queues that let you execute effects in sequence, but what I really needed but couldn’t find was a way to delay execution into intervals and give time for some animation to happen. Or I was thinking of doing all the computation up front and making a queue of the intermediate states to be animated independently and more smoothly after all the math had been worked out. I think that a friend of mine’s semester project actually makes use of some animator model to illustrate class diagrams in Java, with there being some function that takes an arbitrary linked list of actions to execute in sequence. Would’ve been nice to have some time to figure that out.

I ended up using setTimeout to call a function on each row of the matrix with a fixed delay. This is most likely less than ideal because in order to make it work, I had to invoke the method on the object from the global scope rather than something nice. Like what? I don’t know. I had the urge to just pass a function that has the this pointer pointing to the object. I was also wondering about passing the member function to setTimeout, but that felt awkward to even think about.

Features I’d include if I had more time would be a way to input your own matrix of values and an easy way to select the pivot strategy to use on the fly.

BAD Math Day Weekend

I attended yet another BAD Math Day (Bay Area Discrete Math meeting) today. I’ve probably been to four of these, and each time I’ve been equally left in the dust in terms of comprehending anything any speaker says, the best moments being when the speaker mentions a definition that is partially familiar to me from past/current coursework and when the speaker jokingly takes two minutes to remind the “one person in the room” (\me smiles) who doesn’t know of some presumably elementary math concept. So there was nothing out of the ordinary this time.

I think the one thing that stuck to me most was the talk given by the guy from Lawrence Livermore Labs, which introduced me to a bit of game theory in the form of Stackelberg and Nash games, and we also saw some of the algorithms for solving the related optimization problems, with familiar sounding techniques like branch and bound being mentioned. The guy was giving a talk on how counterterrorists and terrorists play this game of trying to one-up the other with probabilities associated to decisions like target area of attack, mode of attack, and all these parameters that sound like you could have a whole lot of fun writing a simulation for, possibly in the form of a Civilization scenario.

Since I didn’t really get much out of it as far as content goes, I paid attention to what I could do as a human being, which is to watch for examples of good speech making. I’m pretty jealous of skilled speakers in general: it is a nontrivial thing to be able to sustain a presentation that makes sense and keeps people paying attention, both for much longer than 5 minutes. The linear optimization guy who talked about computational complexity this time around was skipping tons of slides to get through everything in 30 minutes. You could tell that he knew how much he had to talk about and you’d feel like you could follow as he led you along. Smooth delivery like that can only mean having given that talk a bunch of times before. Of course there was also the not-so-good parts as I guess is to be expected after letting x number of scientists/mathematicians on stage. I think nervousness is pretty transparent on the speaker.

So besides wishing that someday I can possibly understand a little more in these talks, I am wishing that I might make more sense when I talk out loud as well. I’m in for the general GRE this coming week, and I’m putting an honest effort in preparing for that essay part. Screw the vocab, though.