Cyclic Knight's Tour Solutions

These are paths that a "knight" (chess game piece) can take on a chess board using only legal moves so that every square on the board is covered once and only once. They are cyclic because the last move is one legal move from the first.

[image]

Computing these has been an occasional fascination of mine ever since I wrote my first program in assembly language on a 2MHz 8080 (8-bit microprocessor) in 1978. That program, using a classic recursive backtracking algorithm, eventually found one solution after running for about a week.

The problem is interesting because there are so many possibilities to test and the many blind alleys which lead almost to a solution are so long and time-consuming. (A solution is basically a 64 digit base 8 number). I find it fascinating that this problem, which is so extremely difficult for a person (or even a straightforward computer program) to solve, turns out to have so many solutions. Using my best program in 1992 on 486-class hardware I easily found tens of thousands of cyclic solutions and 1.2 million non-cyclic solutions. Writing a good program is a fun exercise.

Notice that the solutions (at least the ones I find) all have a somewhat similar appearance but like the proverbial snowflake, each is unique.