Abstract | ||
---|---|---|
We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1 x 2 pieces on a hexagonal grid board of 2n + 1 cells with n pieces, using sliding, turning and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant. |
Year | DOI | Venue |
---|---|---|
2020 | 10.4230/LIPIcs.ISAAC.2020.33 | ISAAC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joep Hamersma | 1 | 0 | 0.34 |
Marc van Kreveld | 2 | 0 | 0.68 |
yushi uno | 3 | 222 | 28.80 |
Tom C. van der Zanden | 4 | 8 | 6.94 |