Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2503.10393 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |