Nondango is NP-Complete
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917596712927232 |
|---|---|
| author | Ruangwises, Suthee |
| author_facet | Ruangwises, Suthee |
| contents | Nondango is a pencil puzzle consisting of a rectangular grid partitioned into regions, with some cells containing a white circle. The player has to color some circles black such that every region contains exactly one black circle, and there are no three consecutive circles (horizontally, vertically, or diagonally) having the same color. In this paper, we prove that deciding solvability of a given Nondango puzzle is NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11447 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Nondango is NP-Complete Ruangwises, Suthee Computational Complexity Nondango is a pencil puzzle consisting of a rectangular grid partitioned into regions, with some cells containing a white circle. The player has to color some circles black such that every region contains exactly one black circle, and there are no three consecutive circles (horizontally, vertically, or diagonally) having the same color. In this paper, we prove that deciding solvability of a given Nondango puzzle is NP-complete. |
| title | Nondango is NP-Complete |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2310.11447 |