HackerPapers

arXiv:1909.02849cs.CC

NP-completeness of the game Kingdomino

Viet-Ha Nguyen, Kevin Perrot, Mathieu Vallet

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

Kingdomino is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place $2 \times 1$ dominoes on a grid layout, and get a better score than other players. Each $1 \times 1$ domino cell has a color that must match at least one adjacent cell, and an integer number of crowns (possibly none) used to compute the score. We prove that even with full knowledge of the future of the game, in order to maximize their score at Kingdomino, players are faced with an NP-complete optimization problem.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.DMDiscrete Mathematics

On Hacker News

No comments linking this paper were found in the collected sources. Found in 2 HN submissions from Sep 2019 to Jul 2020. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.