Rikudo is NP-complete - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2021

Rikudo is NP-complete

Rikudo est NP-complet

(1) , (2)
1
2

Abstract

Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). We prove that the game is complete for NP, even if the puzzle has no hole. When all odd numbers are placed it is in P, whereas it is still NP-hard when all numbers of the form $3k+1$ are placed.

Dates and versions

hal-03512769 , version 1 (05-01-2022)

Identifiers

Cite

Viet-Ha Nguyen, Kévin Perrot. Rikudo is NP-complete. [Research Report] Inria; Université Côte d'Azur; I3S; CNRS. 2021. ⟨hal-03512769⟩
17 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More