Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913734761381888 |
|---|---|
| author | Takahata, Takuma Minamikawa, Norito Okuno, Takayuki |
| author_facet | Takahata, Takuma Minamikawa, Norito Okuno, Takayuki |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10393 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational Complexity and Integer Programming Formulation of the Oredango Puzzle Takahata, Takuma Minamikawa, Norito Okuno, Takayuki Computational Complexity 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. |
| title | Computational Complexity and Integer Programming Formulation of the Oredango Puzzle |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2503.10393 |