2025/03/13 by Takahata, Takuma, Minamikawa, Norito, Okuno, Takayuki
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.10393
Oredango puzzle, one of the pencil puzzles, was originally created by Kanaiboshi and published in the popular puzzle magazine Nikoli. In this paper, we show NP- and ASP-completeness of Oredango by constructing a reduction from the 1-in-3SAT problem. Next, we formulate Oredango as an 0-1 integer-programming problem, and present numerical results obtained by solving Oredango puzzles from Nikoli and PuzzleSquare JP using a 0-1 optimization solver.