2020/11/02 by Hamersma, Joep, van Kreveld, Marc, Uno, Yushi +1 · 1 citation
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.1.3 #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2011.00968
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.