Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
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 a 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.
Authors
- Norito Minamikawa (ORCID: https://orcid.org/0000-0002-0475-549X)
- Takayuki Okuno (ORCID: https://orcid.org/0000-0003-2178-1494)
- Takuma Takahata
Institutions
- Seikei University (JP)
- Shizuoka Institute of Science and Technology (JP)
Publication Details
- Journal
- IEICE Transactions on Information and Systems
- Published
- 2025-08-18
- DOI
- https://doi.org/10.1587/transinf.2025fcp0008
- Primary Topic
- Evolutionary Algorithms and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Japan Society for the Promotion of Science