Leprechauns on the chessboard
Publication Type:
Refereed Original Article
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.
Digital Object Identifer (DOI):
10.1016/j.disc.2021.112316
Publication Status:
Published
Date Accepted for Publication:
Friday, 15 January, 2021
Publication Date:
01/05/2021
Journal:
Discrete Mathematics
Volume:
344
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
Yes
Publication document: