Rolling a Die over a Labeled Board

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A unit cube has its faces labeled $1,\ldots,6$ as a die. It starts on a square of the integer grid at the corner of a rectangular board $R$, with edges parallel to the axes. Every square of $R$ has a prescribed label in $\{1,\ldots,6\}$. A move rolls the cube by a quarter-turn over one of its bottom edges to an adjacent board square. There are no free cells: each board square must be visited exactly once, and its label must equal the cube's upper face on that visit.

Statement recorded in the supplied source.

Determine the computational complexity of deciding whether a legal rolling sequence exists for a fully labeled rectangular board with the prescribed starting die. If a solution exists, is the fully labeled board uniquely rollable? [S2]

Short English statement

Determine the computational complexity of deciding whether a legal rolling sequence exists for a fully labeled rectangular board with the prescribed starting die. If a solution exists, is the fully labeled board uniquely rollable?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 5500068 (AMR-054-0068). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke (editors), The Open Problems Project, maintained original source, Problem 68, Statement and complete Partial/Related Results. https://github.com/edemaine/topp/blob/main/Problems/P.000068.