Leprechauns on the chessboard

Simple item page
dc.contributor.authorEscamocher, Guillaume
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2021-02-19T15:48:50Z
dc.date.available2021-02-19T15:48:50Z
dc.date.issued2021-02-05
dc.date.updated2021-02-19T15:38:40Z
dc.description.abstractWe 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.en
dc.description.sponsorshipScience Foundation Ireland (under Grant number 12/RC/2289-P2, which is co-funded under the European Regional Development Fund)en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.articleid112316en
dc.identifier.citationEscamocher, G. and O’Sullivan, B. (2021) 'Leprechauns on the chessboard', Discrete Mathematics, 344(5), 112316 (17 pp). doi: 10.1016/j.disc.2021.112316en
dc.identifier.doi10.1016/j.disc.2021.112316en
dc.identifier.endpage17en
dc.identifier.issn0012-365X
dc.identifier.issued5en
dc.identifier.journaltitleDiscrete Mathematicsen
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/11079
dc.identifier.volume344en
dc.language.isoenen
dc.publisherElsevieren
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://www.sciencedirect.com/science/article/pii/S0012365X21000297
dc.rights© 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectAssignment diversityen
dc.subjectConstraint satisfactionen
dc.subjectn-Queens Problemen
dc.titleLeprechauns on the chessboarden
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
1-s2.0-S0012365X21000297-main.pdf
Size:
585.33 KB
Format:
Adobe Portable Document Format
Description:
Published version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles