Rolling Cubes

A standard die is placed at the bottom-left corner of a $3 \times 3$ grid with face $1$ upward, face $2$ towards the north, and face $3$ towards the east. The die rolls, one cell at a time, onto an adjacent cell; a roll cycles four of the six faces (the top, the bottom, and the two faces in the direction of travel) and leaves the two faces parallel to the roll axis fixed. A tour is a Hamiltonian path on the $3 \times 3$ grid: the die visits each of the nine cells exactly once. Each visited cell records the face that happens to be on top at the moment of the visit. We ask: what is the maximum, and the minimum, total of the nine recorded top faces over all legal tours?

The puzzle is an integer rolling-cube search in the tradition of Berlekamp, Conway, and Guy’s Winning Ways (Volume $4$ , games on grids). Its combinatorial shape is a Hamiltonian path problem with a side-state (die orientation) that evolves locally. Both features are natural for CP-SAT: the tour is a permutation constraint; the die state is an $\operatorname{AllowedAssignments}$ table of $24 \cdot 4 = 96$ transition tuples.

Die orientations and their transitions

A standard die has three pairs of opposite faces: $\{1, 6\}$ , $\{2, 5\}$ , $\{3, 4\}$ . The cube has twenty-four rotational orientations, each specified completely by the pair $(\text{top}, \text{north})$ with $\text{east}$ derived. We encode each orientation as a triple of face numbers $(t, n, e)$ and enumerate the $24$ valid triples by closure under the four rolls. A roll in direction $D$ sends $(t, n, e)$ to: $\begin{aligned} D = N: \quad &(t', n', e') = (7 - n, \; t, \; e), \\ D = S: \quad &(t', n', e') = (n, \; 7 - t, \; e), \\ D = E: \quad &(t', n', e') = (7 - e, \; n, \; t), \\ D = W: \quad &(t', n', e') = (e, \; n, \; 7 - t). \end{aligned}$

The programming model

Variables

Number the grid cells $0, 1, \ldots, 8$ row-major. Let $c_t \in \{0, \ldots, 8\}$ be the cell visited at time $t \in \{0, \ldots, 8\}$ , with $c_0 = 0$ and all $c_t$ distinct. Let $d_t \in \{N, S, E, W\}$ for $t \in \{0, \ldots, 7\}$ be the rolling direction taken from step $t$ to step $t+1$ , and let $o_t \in \{0, \ldots, 23\}$ be the index of the die’s orientation at step $t$ , with $o_0$ equal to the initial orientation $(1, 2, 3)$ .

Grid transitions

Express cell $c$ as $(r, k) = (c \div 3, c \bmod 3)$ via integer division and modulo. Adjacency in the grid translates directly into equalities on $(r, k)$ : direction $N$ requires $r_{t+1} = r_t + 1$ and $k_{t+1} = k_t$ , and similarly for the other directions.

Die-rolling transitions

The triple $(o_t, d_t, o_{t+1})$ must belong to the precomputed transition table of size $96$ , imposed as an $\operatorname{AllowedAssignments}$ constraint.

Top-face readouts

Let $f_t \in \{1, \ldots, 6\}$ be the top-face value at step $t$ . Link $f_t$ to $o_t$ by a table constraint $(o_t, f_t) \in \{(i, \text{top}(O_i)) : i = 0, \ldots, 23\}$ .

Objective

Maximise or minimise $\sum_{t = 0}^{8} f_t$ .

A solver in sixty lines

from ortools.sat.python import cp_model

OPP = {1: 6, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}

def roll(o, d):
    t, n, e = o
    if d == 'N': return (OPP[n], t, e)
    if d == 'S': return (n, OPP[t], e)
    if d == 'E': return (OPP[e], n, t)
    return (e, n, OPP[t])

def orientations():
    pool = {(1, 2, 3)}
    frontier = set(pool)
    while frontier:
        nxt = set()
        for o in frontier:
            for d in "NSEW":
                r = roll(o, d)
                if r not in pool:
                    pool.add(r); nxt.add(r)
        frontier = nxt
    return sorted(pool)

def solve(objective="max"):
    O = orientations()
    idx = {o: i for i, o in enumerate(O)}
    trans = [(i, di, idx[roll(O[i], d)])
             for i in range(24)
             for di, d in enumerate("NSEW")]
    top_tbl = [[i, O[i][0]] for i in range(24)]

    m = cp_model.CpModel()
    c = [m.NewIntVar(0, 8, "") for _ in range(9)]
    m.AddAllDifferent(c)
    m.Add(c[0] == 0)
    r = [m.NewIntVar(0, 2, "") for _ in range(9)]
    k = [m.NewIntVar(0, 2, "") for _ in range(9)]
    for t in range(9):
        m.AddDivisionEquality(r[t], c[t], 3)
        m.AddModuloEquality(k[t], c[t], 3)

    d = [m.NewIntVar(0, 3, "") for _ in range(8)]
    o = [m.NewIntVar(0, 23, "") for _ in range(9)]
    m.Add(o[0] == idx[(1, 2, 3)])
    f = [m.NewIntVar(1, 6, "") for _ in range(9)]

    for t in range(8):
        isN = m.NewBoolVar(""); isS = m.NewBoolVar("")
        isE = m.NewBoolVar(""); isW = m.NewBoolVar("")
        for v, b in zip(range(4), [isN, isS, isE, isW]):
            m.Add(d[t] == v).OnlyEnforceIf(b)
            m.Add(d[t] != v).OnlyEnforceIf(b.Not())
        m.AddBoolOr([isN, isS, isE, isW])
        m.Add(r[t + 1] == r[t] + 1).OnlyEnforceIf(isN)
        m.Add(k[t + 1] == k[t]).OnlyEnforceIf(isN)
        m.Add(r[t + 1] == r[t] - 1).OnlyEnforceIf(isS)
        m.Add(k[t + 1] == k[t]).OnlyEnforceIf(isS)
        m.Add(r[t + 1] == r[t]).OnlyEnforceIf(isE)
        m.Add(k[t + 1] == k[t] + 1).OnlyEnforceIf(isE)
        m.Add(r[t + 1] == r[t]).OnlyEnforceIf(isW)
        m.Add(k[t + 1] == k[t] - 1).OnlyEnforceIf(isW)
        m.AddAllowedAssignments(
            [o[t], d[t], o[t + 1]], trans)

    for t in range(9):
        m.AddAllowedAssignments([o[t], f[t]], top_tbl)

    total = m.NewIntVar(0, 54, "")
    m.Add(total == sum(f))
    if objective == "max": m.Maximize(total)
    else:                   m.Minimize(total)
    s = cp_model.CpSolver(); s.Solve(m)
    return s.Value(total), [s.Value(f[t]) for t in range(9)]

The maximum total is $\mathbf{37}$ , achieved by the tour shown in Figure 14.1; the minimum is $\mathbf{25}$ , achieved by Figure 14.2. Both are found in about $20$ milliseconds.

*Maximum tour ( $\sum f_t = 37$ ). Numbers in warm orange show the top face at the moment of visit; the small number above indicates the visit order.*

Sources. Rolling-cube puzzles are a long-running theme in recreational mathematics. Martin Gardner’s Scientific American column ( $1963$ , “Dice tricks”) posed a number of rolling-cube questions on $3 \times 3$ and $4 \times 4$ boards; Berlekamp, Conway, and Guy’s Winning Ways for Your Mathematical Plays (Volume $4$ , second edition, $2004$ ) devotes a chapter to the rolling block family, which includes the present tour puzzle as an integer variant. The specific form — Hamiltonian tour with extremal top-face sum — appears to have been popularised by I. Stewart in his Guardian column in the $1990$ s. The generalisation to $4 \times 4$ and larger grids remains a clean CP-SAT exercise; the search space grows roughly by a factor of $\sim\!10$ per grid-edge length, and the same model solves the $4 \times 4$ extremal problem in seconds.