Rolling a die over a fully labelled board
Label the faces of a unit cube with $1, \dots, 6$ as on a die, and stand it on the integer lattice in the plane with one corner at the origin and its edges parallel to the axes. A rectangular board $R$ of unit lattice squares, with a corner at the origin, has every square labelled by a number from $\{1, \dots, 6\}$. The cube moves by rolling over one of its edges. The goal is a sequence of rolls in which the cube lands on every square $s$ of $R$ exactly once, with the label of $s$ on its top face when it does.
O'Rourke first posed a version in which only some connected set of squares is labelled and all other squares are free: they may be visited any number of times, with any face on top. Buchin, Buchin, Demaine, Demaine, El-Khechen, Fekete, Knauer, Schulz and Taslakian proved that version NP-complete. They left open whether a solvable fully labelled board always has a unique solution (with blocked squares allowed, it need not); this has been settled for boards with side lengths at most $8$.
Problem. How hard is this puzzle computationally: given a fully labelled rectangular board $R$, what is the complexity of finding such a sequence of rolls, or of determining that none exists?
Source: O'Rourke (CCCG 2005), see Demaine and O'Rourke (2006); developed by Buchin, Buchin, Demaine, Demaine, El-Khechen, Fekete, Knauer, Schulz and Taslakian (2007); Problem 68 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Keywords
- computational complexity, grid puzzle, rolling cube puzzle, The Open Problems Project
References
@inproceedings{demaine2006,
author = {Demaine, Erik D. and O'Rourke, Joseph},
title = {Open problems from {CCCG} 2005},
booktitle = {Proc. 18th Canad. Conf. Comput. Geom.},
year = {2006},
pages = {75--80},
}
@inproceedings{buchin2007,
author = {Buchin, Kevin and Buchin, Maike and Demaine, Erik D. and Demaine, Martin L. and El-Khechen, Dania and Fekete, S{\'a}ndor and Knauer, Christian and Schulz, Andr{\'e} and Taslakian, Perouz},
title = {On rolling cube puzzles},
booktitle = {Proc. 19th Canad. Conf. Comput. Geom.},
year = {2007},
pages = {141--148},
}
@incollection{vandeventer2004,
author = {van Deventer, M. Oskar},
title = {Rolling block mazes},
editor = {Cipra, Barry and Demaine, Erik D. and Demaine, Martin L. and Rodgers, Tom},
booktitle = {A Tribute to a Mathemagician},
publisher = {A K Peters},
year = {2004},
pages = {241--250},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01104, "Rolling a die over a fully labelled board", clopen.solutions.