Knight's Tour
The Knight's tour is an interesting programming puzzle based on the board and "knight" piece from the game of chess. The rules of the puzzle are as follows:
- Your starting position on the board is randomly selected.
- You can only move in the L-shaped movement of a knight in chess. (2 squares, then 1 perpendicular, or 1 then 2)
- You can only move to each square on the board once per game
- The objective is to move to all the squares on the board without repeating any
What makes this an interesting programming challenge is to attempt to enhance the logic in such a way as to increase the chances that the tour will "complete" by moving to all the squares without running out of moves.
The simulation below is an AJAX/PHP based knight's tour. It supports () modes of operation to date.
The simulation below is an AJAX/PHP based knight's tour. It supports () modes of operation to date.
- MODE 1 This method simply selects the first available free square starting with looking "north" and moving clockwise. The highest I have seen it acheive is 50 moves before getting dead locked
- MODE 2 This mode is also a "first available" method, meaning it takes the first open square it finds. However in this case we examine the current position and re-order the direction in which we search for free squares. It still follows a clockwise rotation but it breaks the board into 4 equal sized quadrents and alters the starting point of that rotation based on the current position. Testing has proved that it sometimes bombs out at < 10 moves, but that it also acheives higher scores than mode 1. Interesting...
- Mode 3 This mode is like mode 1, except it shuffles the directions and chooses a random first availble direction. Sometimes it does well, mostly it does not so well.
