The Colour Fairies

Five fairies drift through a nursery on five nights, and each is smitten with a single colour. Above each sleeping child hangs a little cluster of coloured stars, and when a visiting fairy finds her colour among a child’s stars she leaves a pearl behind. We are not told which colour any fairy loves; we are told only the stars each child displays, the count of pearls each child woke to on each night, and which fairies flew on which night. From that we are to name every fairy’s colour. The puzzle is Dennis Shasha’s, and the integer-programming treatment is Chlond’s sequel to his shifty-witnesses lie detector; once more the trick is to let the unknown loves and the known counts share one program and force them to agree.

The puzzle

There are three children, Tyler, Jordan and David, and nine colours: silver, sage, gold, rose, turquoise, ivory, violet, emerald and earth. The stars above each child are fixed for the week, $$\begin{array}{ll} \text{Tyler:} & \text{rose, turquoise, violet} \\ \text{Jordan:} & \text{sage, ivory, violet} \\ \text{David:} & \text{sage, violet, emerald.} \end{array}$$ Five fairies, Cloe, Ariana, Oliviana, Anya and Caroline, visit on the nights $$\begin{array}{ll} \text{Cloe:} & 1,4,5 \qquad \text{Ariana:}\ 3,4 \qquad \text{Oliviana:}\ 2,4,5 \\ \text{Anya:} & 1,2,3,5 \qquad \text{Caroline:}\ 1,2,3, \end{array}$$ and the pearls found the next morning, child by child over nights $1$ to $5$, were $$\text{Tyler } (1,0,0,1,1), \quad \text{Jordan } (1,2,1,1,2), \quad \text{David } (2,2,2,0,1).$$ Two facts close the puzzle: at least one fairy loves turquoise, and exactly one loves earth. Which colour does each fairy love?

The model

Each fairy loves one colour, so the natural unknown is a grid. Write $x_{i,k}=1$ when fairy $i$ loves colour $k$, and ask each row to choose exactly one colour, $$\sum_{k} x_{i,k} = 1 \qquad (\text{each fairy } i).$$ The pearls do the rest. Let $s_{j,k}=1$ when child $j$ displays a star of colour $k$, and $v_{i,m}=1$ when fairy $i$ visits on night $m$. On night $m$ child $j$ gains a pearl from every visiting fairy whose colour sits among the child’s stars, so the morning’s tally $p_{j,m}$ must satisfy $$\sum_{i}\sum_{k} v_{i,m}\,s_{j,k}\,x_{i,k} = p_{j,m} \qquad (\text{each child } j,\ \text{night } m).$$ The product looks quadratic but is not: $v_{i,m}$ and $s_{j,k}$ are known numbers, and only $x_{i,k}$ is a variable, so every one of these fifteen constraints is linear. Two cardinality clues finish the statement, $$\sum_{i} x_{i,\,\text{turquoise}} \ge 1, \qquad \sum_{i} x_{i,\,\text{earth}} = 1 .$$ There is nothing to maximise; any grid obeying every line is the answer.

The whole clue set as one matrix

It is worth seeing the pearl constraints whole. Gather the loves into a $5\times 9$ matrix $X$ (fairies by colours), the stars into a $3\times 9$ matrix $S$ (children by colours), and the visits into a $5\times 5$ matrix $V$ (fairies by nights). Then $SX^{\top}$ is a $3\times 5$ matrix whose $(j,i)$ entry is $1$ exactly when fairy $i$ pleases child $j$, since each fairy’s row of $X$ holds a single one; multiplying by $V$ sums those over the night’s visitors. The fifteen pearl equations are then the single statement $$S\,X^{\top} V = P,$$ with $P$ the $3\times 5$ pearl table. A whole genre of consistency clue collapses to one matrix product, which is how the puzzle is most naturally laid out in a spreadsheet, and a reminder that sigma-notation and matrix-notation are two readings of the same constraint.

The solver

from ortools.sat.python import cp_model

COLORS = ["silver", "sage", "gold", "rose", "turquoise",
          "ivory", "violet", "emerald", "earth"]
FAIRIES = ["Cloe", "Ariana", "Oliviana", "Anya", "Caroline"]
star = [[0, 0, 0, 1, 1, 0, 1, 0, 0],   # Tyler
        [0, 1, 0, 0, 0, 1, 1, 0, 0],   # Jordan
        [0, 1, 0, 0, 0, 0, 1, 1, 0]]   # David
pearl = [[1, 0, 0, 1, 1], [1, 2, 1, 1, 2], [2, 2, 2, 0, 1]]
visit = [[1, 0, 0, 1, 1], [0, 0, 1, 1, 0], [0, 1, 0, 1, 1],
         [1, 1, 1, 0, 1], [1, 1, 1, 0, 0]]

def solve_fairies():
    F, H, C, N = 5, 3, 9, 5
    m = cp_model.CpModel()
    x = {(i, k): m.NewBoolVar("")
         for i in range(F) for k in range(C)}
    # each fairy loves exactly one colour
    for i in range(F):
        m.Add(sum(x[i, k] for k in range(C)) == 1)
    # pearls each night match the visits and the stars
    for j in range(H):
        for t in range(N):
            got = sum(visit[i][t] * star[j][k] * x[i, k]
                      for i in range(F) for k in range(C))
            m.Add(got == pearl[j][t])
    # at least one turquoise, exactly one earth
    m.Add(sum(x[i, 4] for i in range(F)) >= 1)
    m.Add(sum(x[i, 8] for i in range(F)) == 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    out = {}
    for i in range(F):
        k = next(c for c in range(C) if s.Value(x[i, c]))
        out[FAIRIES[i]] = COLORS[k]
    return out

The program reads off the unique loves of Figure 59.1: Cloe loves turquoise, Ariana earth, Oliviana ivory, Anya sage and Caroline emerald. No other grid satisfies every line, so the answer is forced.

Reading the deduction

The pearls never see a fairy’s colour directly, only which children it pleases. A colour is therefore known to the tallies merely by its please-signature, the triple recording whether it sits among Tyler’s, Jordan’s and David’s stars. Sorting the nine colours by that signature is telling: $$\begin{array}{ll} (1,0,0): & \text{rose, turquoise} \\ (0,1,1): & \text{sage} \\ (0,1,0): & \text{ivory} \\ (0,0,1): & \text{emerald} \\ (1,1,1): & \text{violet} \\ (0,0,0): & \text{silver, gold, earth.} \end{array}$$ Four of the signatures belong to a single colour, but two are shared: rose and turquoise please exactly Tyler, and silver, gold and earth please no one. The pearl tallies pin each fairy’s signature, and so they pin outright the three fairies whose signature is unique to its colour: Oliviana must be the lone ivory, Anya the lone sage, Caroline the lone emerald. They cannot, however, separate fairies inside a shared class. Cloe’s signature is $(1,0,0)$, leaving her rose or turquoise; Ariana’s is $(0,0,0)$, leaving her silver, gold or earth. The counts alone thus admit $2\times 3 = 6$ readings of the nursery, all pleasing the children identically.

This is where the two soft clues earn their place, and they are placed with care. “At least one turquoise” can be honoured by no fairy but Cloe, the only one with turquoise in reach, so it forces Cloe to turquoise and settles her class. “Exactly one earth” can be met by no fairy but Ariana, so it forces Ariana to earth and settles hers. Each clue names one colour inside one shared class and breaks that tie alone; drop either and the count of consistent nurseries climbs back from one to three or to two. The hard data fixes the structure, the loves the children can feel, and the soft data supplies the two labels the structure leaves free, a division this book has met before and will meet again.

Sources. The puzzle and its integer program follow Martin J. Chlond, Puzzle—O.R. with the Fairies, INFORMS Transactions on Education volume $8$, number $2$ ($2008$), pages $100$–$102$; the matrix reading $SX^{\top}V=P$ is his. It is the sequel to his shifty-witnesses lie detector of the previous year. The puzzle is Dennis E. Shasha’s, from Puzzling Adventures (W. W. Norton, $2005$) and first set in his Scientific American column of April $2002$. The loves recovered here, the uniqueness of that reading, the six pearl-only readings and their $2\times 3$ structure, the partition of the colours by please-signature, and the necessity of each cardinality clue are checked by exhaustion over all $9^{5}=59{,}049$ colourings.