Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917828081221632 |
|---|---|
| author | Minevich, Igor Cunningham, Gabe Karan, Aditya Gyllinsky, Joshua V. |
| author_facet | Minevich, Igor Cunningham, Gabe Karan, Aditya Gyllinsky, Joshua V. |
| contents | The Parks Puzzle is a paper-and-pencil puzzle game that is classically played on a square grid with different colored regions (the parks). The player needs to place a certain number of "trees" in each row, column, and park such that none are adjacent, even diagonally. We define a doubly-infinite family of such puzzles, the $(c, r)$-tree Parks puzzles, where there need be $c$ trees per column and $r$ per row. We then prove that for each $c$ and $r$ the set of $(c, r)$-tree puzzles is NP-complete. For each $c$ and $r$, there is a sequence of possible board sizes $m \times n$, and the number of possible puzzle solutions for these board sizes is a doubly-infinite generalization of OEIS sequence A002464, which itself describes the case $c = r = 1$. This connects the Parks puzzle to chess-based puzzle problems, as the sequence describes the number of ways to place non-attacking kings on a chessboard so that there is exactly one in each column and row (i.e. to place non-attacking dragon kings in shogi). These findings add yet another puzzle to the set of chess puzzles and expands the list of known NP-complete problems described. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02251 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464 Minevich, Igor Cunningham, Gabe Karan, Aditya Gyllinsky, Joshua V. Computational Complexity Combinatorics The Parks Puzzle is a paper-and-pencil puzzle game that is classically played on a square grid with different colored regions (the parks). The player needs to place a certain number of "trees" in each row, column, and park such that none are adjacent, even diagonally. We define a doubly-infinite family of such puzzles, the $(c, r)$-tree Parks puzzles, where there need be $c$ trees per column and $r$ per row. We then prove that for each $c$ and $r$ the set of $(c, r)$-tree puzzles is NP-complete. For each $c$ and $r$, there is a sequence of possible board sizes $m \times n$, and the number of possible puzzle solutions for these board sizes is a doubly-infinite generalization of OEIS sequence A002464, which itself describes the case $c = r = 1$. This connects the Parks puzzle to chess-based puzzle problems, as the sequence describes the number of ways to place non-attacking kings on a chessboard so that there is exactly one in each column and row (i.e. to place non-attacking dragon kings in shogi). These findings add yet another puzzle to the set of chess puzzles and expands the list of known NP-complete problems described. |
| title | Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464 |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2411.02251 |