Abstract
Euler, Vandermonde, Dudeney, Schwesk, Berliner, Conrad and many others already considered knight's tours on chessboards. The classical knight's tour problem consist of finding out on a N × M chessboard a sequence of legal knight moves that visit every cell exactly once and finish by returning to the initial cell. A more challenging question is to generalise the problem to more than one knight. More precisely, we search for a partitioning of the m x n chessboard by a set of C cycles in such a way that each cell belongs to one single cycle. Moreover we impose all the cycles to be balanced. Since a cycle can't have an odd number of cells, we enforce that each cycle visits between 2 x floor(floor((m x n) / c) / 2) and 2 x cell(cell((m x n) / c) / 2) cells. We systematically consider all the boards m x n such that 1<m<11, 1<n<11, (m x n) mod 2=0 and we solve the problems for the number of knights c varying between 1 and floor((m x n) / 2). We show how to express this problem with CHIP and prove that for more than one quarter of the 820 instances there is no balanced solution (there is for instance no solution for 6 knights on a 6x6 board such that each knight visits exactly 6 cells).