Leprechauns on the chessboard
We introduce in this paper leprechauns, fairy chess pieces that can move either like the standard queen, or to any tile within k king moves. We then study the problem of placing n leprechauns on an n×n chessboard. When k=1, this is equivalent to the standard n-Queens Problem. We solve the problem for k=2, as well as for k>2 and n≤(k+1)2, giving in the process an upper bound on the lowest non-trivial value of n such that the (k,n)-Leprechauns Problem is satisfiable. Solving this problem for all k would be equivalent to solving the diverse n-Queens Problem, the variant of the n-Queens Problem where the distance between the two closest queens is maximized. While diversity has been a popular topic in other constraint problems, this is not the case for the n-Queens Problem, making our results the first major ones in the domain.
Assignment diversity , Constraint satisfaction , n-Queens Problem
Escamocher, G. and O’Sullivan, B. (2021) 'Leprechauns on the chessboard', Discrete Mathematics, 344(5), 112316 (17 pp). doi: 10.1016/j.disc.2021.112316