Enumerating Knight’s Tours using an Ant Colony Algorithm

Abstract- In this paper we show how an ant colony optimisation algorithm may be used to enumerate knight’s tours for variously sized chessboards. We have used the algorithm to enumerate all tours on 5x5 and 6x6 boards, and, while the number of tours on an 8x8 board is too large for a full enumeration, our experiments suggest that the algorithm is able to uniformly sample tours at a constant, fast rate for as long as is desired.