As a child I was, for a time, fascinated with computers. I even briefly entertained the idea that I would write a game in BASIC. The hours it took me to draw a slightly skewed line across the 16 color monitor of my Atari 800XL dispelled that notion almost as quickly as my prepubescent brain had latched on to it. Fast forward to college and while not a CS major, pursuing a Mathematics degree involved some logic and programming courses. When I say "pursuing" I mean barely attending classes and eventually dropping out completely to instead hitchhike across the continental US with all my belongings on my back and only a vague idea of where I was going. The bits of pascal and logic I did study did not stick with me except as a faint memory. Fast forward 8 years to 1998 and I have a wonderful daughter, a quaint middle management job at a box factory, and a renewed interest in the surging home computer phenomenon going on at the time. So with a brand new Windows 98 machine and a copy of Deitel and Deitel's C++ programming purchased for 10 bucks at a garage sale I set out to learn to write software during lunch breaks and late evening hacking sessions.
I realized after downloading gcc for windows and perusing the documentation that I was way out of my league. It was this experience that prompted me to explore Linux (as well as the limiting nature of how far one can really dig into Windows). But before I did I worked through many chapters of the C++ book, and while not able to execute the examples I spent a lot of time attempting to really grasp the basic concepts. One exercise I found particularly interesting was the Knights Tour puzzle. Played on a 64 square chess board, the player moves a piece around using only the L-shaped movement of the Knight from chess. The initial square is randomly selected and each square can only be moved to once. The goal is to move to all the squares before running out of options.
The specific exercise required that you create and track the board squares with a multi-dimensional array, using a random algorithm to determine the next move. Once functional, runs of several 1000 iterations were to be tested to determine the likelihood of the simulation actually completing the puzzle. The more advanced follow up was to then tweak your random algorithm so as to increase the likelihood of success. Having toyed with this in several programming languages throughout the years, here is a simple version in PHP using AJAX calls to update the board after each move. The next move is selected by simply working clockwise from the current square and taking the first available location. It counts the moves and takes about 20 seconds to complete. So far after only a few tests , 51 moves is the best score I have seen it achieve. You can try it out yourself at:
When I have some time I think it would be fun to try improve the accuracy, and if and when I do I will post more on the subject. Enjoy!
| No Images with this post |
