A back to school programming exercise

For most of us in the States, we're getting back to work after four days of family and tryptophan. For the rest of the world, it's just plain Monday. Any way it goes, a lot of us could use something to get back in gear and could certainly use an interesting activity for our students.

Scrolling through Slashdot on a snowy Sunday afternoon, I stumbled across an interesting exercise for both math and computer science courses. The article describes how one bored coder solved the Knight's tour problem using Python:

"When I was a kid, I used to play the Knight's Tour puzzle with pen and paper: you simply had to pass once from every square of a chess board, moving like a Knight. Nowadays, I no longer play chess; but somehow I remembered this nice little puzzle and coded a 60-line Python solver that can tackle even 100x100 boards in less than a second. Try beating this, fellow coders!"

Many of you may have covered traveling salesmen problems and Euler's Tours with your math classes (if you haven't yet, you can easily kill a day or a week talking about them and the logic and combinatorics involved; better yet, they are usually covered in some rudimentary way on many standardized tests).

The Knight's Tour problem is similar and any would be worth anything from a simple brain teaser (try a Knight's Tour on a small grid or have kids give thought to the Seven Bridges of Königsberg problem) all the way through a full-on set of programming exercises.

Obviously, these problems can be solved with any number of programming languages; the author of the original post, however, does do a nice job of pointing out the elegance of Python. Python certainly had a lot of votes when I asked "What programming language should we teach?" This example certainly gives some ideas why Python was such a popular response.