A Knight's Tour is a path on a chess board such that a knight moving according to the rules of chess will visit each square exactly once. Here is a program that solves the Knight's Tour for various board sizes.
git clone git://github.com/skeeto/knights-tour.git
I wrote it purely for speed, and so in cases where the algorithm doesn't blow up (taking possibly thousands of years to complete) it only takes a few milliseconds to complete. The algorithm is recursive and goes like so,
- Given a board marked with visited spaces and a position create a list of valid moves.
- If the list is empty, return failure.
- Sort of the list ascendingly according to the opportunities of the target space. That is, sort by the number of valid moves that are available from the target space.
- Mark the current space as visited, then recurse from the new position with the new board starting with the first target in the list.
- If the recursion returns success, return success.
- If the recursion returns failure, recurse with the next target in the list, and so on. If all the targets on the list have been tried, return failure.
The purpose of going towards targets with few opportunities is so that we don't leave any stranded spaces that will not be detected until much later. When it does run into a dead end, it usually only has to back out a short ways and try again.
The algorithm breaks down on certain board sizes. For example, try a 120 by 120 board. Instead of nearly instantaneous solution like 120 by 119 would get, it takes enormous amounts of time. I don't yet know why.
Also included in the repository is a Perl script for creating frames for a video. Here are two videos, one for an 8x8 board, one for a 80x80 board.
It's interesting how on the large one the behavior seems to be random at some places, but all it's doing is following that simple algorithm.