The Four Strongest

In the National Museum of Mongolia sits a wooden puzzle of four carved animals, the dragon, the tiger, the lion, and the garuda, the four mythological guardians known as the Four Strongest. Each carving must be laid flat in a shallow box, and the box is only just large enough: the four fit along it in one arrangement and refuse to fit in almost every other. A player may slide a carving in either of two ways, call them up and down, a half turn apart, and may place the four in any order along the box. The question is the order and the turns that pack them into the least length.

With four animals and two turns each, the arrangements number $2^4 \cdot 4! = 384$, and since reversing a row and turning every animal over gives the mirror image of the same packing, the distinct arrangements number $192$. The puzzle’s own author settled it the hard way, by laying out all $192$ and measuring each. An integer program does better, and the saving is not in the search but in the measuring.

A length built from pairs

The length of a row is awkward to measure: there are $192$ rows. But the length of a row of touching shapes is almost decided by its neighbours. When two carvings sit side by side they nest, the bumps of one settling into the hollows of the other, and how far they nest depends only on the two of them and their turns, not on what else is in the box. So write $b(o)$ for the length of a single carving in orientation $o$, and $d(o, o')$ for the length of the touching pair $o$ then $o'$. A row of three, $o_1 o_2 o_3$, is the first pair laid against the second, and the two overlap exactly along the middle carving $o_2$, which the inclusion-exclusion principle says to add once and subtract once: $$L(o_1, o_2, o_3) \;=\; d(o_1, o_2) + d(o_2, o_3) - b(o_2).$$ The pattern continues. The length of the whole row is the sum of the adjacent-pair lengths, with each interior carving’s own length subtracted back out: $$L(o_1, \ldots, o_n) \;=\; \sum_{k=1}^{n-1} d(o_k, o_{k+1}) \;-\; \sum_{k=2}^{n-1} b(o_k).$$ This is exact when the carvings nest along a line, and a close approximation for real two-dimensional shapes, which is the setting the puzzle’s author worked in.

The point of the formula is the measuring it saves. Every row’s length is now known once the single lengths and the pair lengths are known, and those are few: the singles number $\lvert I \rvert \lvert J \rvert = 4 \cdot 2 = 8$, and the ordered pairs of two different carvings, each in either turn, number $\lvert I \rvert (\lvert I \rvert - 1) \lvert J \rvert^2 = 4 \cdot 3 \cdot 4 = 48$. Fifty-six measurements in place of $192$, and the gap widens fast: the arrangements grow faster than any polynomial in the number of carvings, while the measurements grow only as its square.

The model

With the lengths in hand the puzzle is an assignment. Number the positions along the box $0$ to $n - 1$.

Variables

For each carving $i$, turn $j$, and position $k$, a binary variable $$x_{ijk} \in \{0, 1\}$$ takes the value $1$ exactly when carving $i$ lies at position $k$ in turn $j$.

Constraints and objective

Each position holds exactly one carving in one turn, and each carving is placed exactly once: $$\sum_{i, j} x_{ijk} = 1 \quad \forall k, \qquad \sum_{j, k} x_{ijk} = 1 \quad \forall i.$$ The length is a sum over adjacent positions, and a product $x_{ijk}\, x_{i'j'(k+1)}$ records when carving $i$ in turn $j$ sits just left of carving $i'$ in turn $j'$. A product of two binaries is linearised in the standard way by a fresh binary $y$ pinned to their conjunction, $$y \le x_{ijk}, \qquad y \le x_{i'j'(k+1)}, \qquad y \ge x_{ijk} + x_{i'j'(k+1)} - 1,$$ so that $y = 1$ exactly when both placements are made. The objective sums the pair lengths over adjacent positions and subtracts the interior single lengths, the inclusion-exclusion total, and is minimised: $$\text{minimise} \quad \sum_{\substack{i \ne i',\, j, j' \\ k < n - 1}} d\bigl((i, j), (i', j')\bigr)\, y_{ijk i'j'} \;-\; \sum_{\substack{i, j \\ 0 < k < n - 1}} b(i, j)\, x_{ijk}.$$

A solver

The instance below is a self-contained stand-in for the museum’s carvings, whose true measurements are not public. Each carving in each turn is given a left reach and a right reach; its own length $b$ is their sum, and two neighbours nest by the smaller of the touching reaches, so $d = b + b' - \min(\text{left's right reach}, \text{right's left reach})$.

from ortools.sat.python import cp_model

TOYS = ["D", "T", "L", "G"]        # Dragon, Tiger, Lion, Garuda
ORI = ["up", "dn"]
REACH = {                          # (left reach, right reach)
    ("D", "up"): (3, 4), ("D", "dn"): (5, 5),
    ("T", "up"): (4, 5), ("T", "dn"): (2, 5),
    ("L", "up"): (2, 5), ("L", "dn"): (5, 1),
    ("G", "up"): (4, 2), ("G", "dn"): (5, 1),
}
B = {k: h + t for k, (h, t) in REACH.items()}   # own length
def OV(a, c): return min(REACH[a][1], REACH[c][0])
def D(a, c): return B[a] + B[c] - OV(a, c)      # pair length

def shortest_row():
    I, J, K = TOYS, ORI, range(len(TOYS))
    m = cp_model.CpModel()
    x = {(i, j, k): m.NewBoolVar("")
         for i in I for j in J for k in K}
    for k in K:                    # one (toy, turn) per spot
        m.Add(sum(x[i, j, k] for i in I for j in J) == 1)
    for i in I:                    # each toy placed once
        m.Add(sum(x[i, j, k] for j in J for k in K) == 1)
    pairs = [(i, j, p, q) for i in I for j in J
             for p in I for q in J if p != i]
    cost = []
    for k in list(K)[:-1]:         # add adjacent-pair lengths
        for (i, j, p, q) in pairs:
            y = m.NewBoolVar("")
            m.Add(y <= x[i, j, k])
            m.Add(y <= x[p, q, k + 1])
            m.Add(y >= x[i, j, k] + x[p, q, k + 1] - 1)
            cost.append(D((i, j), (p, q)) * y)
    for k in K:                    # subtract interior singles
        if 0 < k < len(TOYS) - 1:
            for i in I:
                for j in J:
                    cost.append(-B[(i, j)] * x[i, j, k])
    m.Minimize(sum(cost))
    s = cp_model.CpSolver()
    s.Solve(m)
    row = [None] * len(TOYS)
    for (i, j, k), v in x.items():
        if s.Value(v):
            row[k] = (i, j)
    return int(s.ObjectiveValue()), row

On this instance the shortest row has length $15$, the dragon and tiger upright leading the lion and garuda turned over: $D\!\uparrow$, $G\!\uparrow$, $T\!\downarrow$, $L\!\downarrow$. It is the only shortest row up to the mirror symmetry, as a sweep of all $192$ arrangements confirms, and the integer program finds it directly without enumerating them.

The museum puzzle itself, with the carvings’ real proportions recovered from photographs, packs shortest as tiger, dragon, lion, garuda in turns up, up, up, down, a published length of about $29.08$ centimetres; the hand-found arrangement the puzzle is usually solved by, dragon, lion, tiger, garuda turned down, up, down, up, measures about $31.54$ under the same data. Those numbers rest on measurements taken off photographs of carvings in a glass case, so the chapter does not reproduce them; what carries across exactly is the shape of the argument, a length read off pairs and a placement read off an assignment.

Sources. The Four Strongest is a puzzle in the collection of the National Museum of Mongolia, described and solved by exhaustive hand arrangement by Uuganbaatar Ninjbat, “The Four Strongest” at the National Museum of Mongolia, The Mathematical Intelligencer volume $42$, number $2$ ($2020$), pages $9$–$14$, who counts the $192$ candidate arrangements; the puzzle also appears as the “Four Dignities.” The integer-programming treatment, the inclusion-exclusion length and the $56$-measurement count, the assignment model with linearised adjacencies, and the $29.08$ and $31.54$ centimetre figures are due to Bismark Singh, Puzzle—A Mathematical Programming Approach for Mongolia’s “The Four Strongest” Puzzle, INFORMS Transactions on Education volume $25$, number $3$ ($2025$), pages $265$–$269$, who works from photograph-derived measurements and a rectangular approximation of the museum’s hexagonal box. The standard linearisation of a product of binaries by a single conjunction variable is the McCormick envelope, after Garth P. McCormick, Computability of Global Solutions to Factorable Nonconvex Programs, Mathematical Programming volume $10$ ($1976$), pages $147$–$175$. The illustrative instance and its unique shortest row are produced and cross-checked by the model above against a full sweep of the $192$ arrangements.