Leprechauns on the chessboard

Loading...
Thumbnail Image
Files
Date
2021-02-05
Authors
Escamocher, Guillaume
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Research Projects
Organizational Units
Journal Issue
Abstract
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.
Description
Keywords
Assignment diversity , Constraint satisfaction , n-Queens Problem
Citation
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