Skip to Main content Skip to Navigation
Journal articles

NP-completeness of the game Kingdomino

Viet-Ha Nguyen 1, 2, 3 Kévin Perrot 4, 3 Mathieu Vallet 4
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
2 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
4 CANA - Calcul Naturel
LIS - Laboratoire d'Informatique et Systèmes
Abstract : Kingdomino is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place 2×1 dominoes on a grid layout, and get a better score than other players. Each 1×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.
Complete list of metadata

https://hal.inria.fr/hal-03121418
Contributor : Ha Nguyen Connect in order to contact the contributor
Submitted on : Tuesday, January 26, 2021 - 1:42:27 PM
Last modification on : Thursday, January 20, 2022 - 5:28:59 PM

Links full text

Identifiers

Citation

Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet. NP-completeness of the game Kingdomino. Theoretical Computer Science, Elsevier, 2020, 822, pp.23-35. ⟨10.1016/j.tcs.2020.04.007⟩. ⟨hal-03121418⟩

Share

Metrics

Les métriques sont temporairement indisponibles