Capital Area Theory Seminar

We describe a divide-and-conquer algorithm for finding closed knight's tours on an n H n chessboard that is simple, efficient and elegant. The algorithm can be used to find quadrisected tours for all even n $ 8, tours invariant under a 180 degree rotation whenever they exist (for all even n $ 8), and tours invariant under a 90 degree rotation whenever they exist (for all n $ 10 congruent to 2 modulo 4). We compare the algorithm experimentally with two existing algorithms, including a neural network due to Takefuji and Lee, a random walk due to Euler and Warnsdorff. We prove the following run-times for our new algorithm: O(n²) on a sequential computer, O(n²/p) on a bounded degree network with p processors for all p=O(n²/log n), O(n²/p²) on a p H p mesh for all p # n^2/3, O(1) on an n H n mesh with row and column CREW buses, and O(1) on a CREW PRAM with O(n²) processors. We further use the algorithm to obtain exponential lower bounds on the number of knight's tours.