Solving Madrigal Solving Madrigal

Introduction

One occasionally encounters a puzzle that seems impossible at first glance, but grows increasingly tractable over time, as its subsidiary components are chipped away step by painstaking step, and the entire framework finally reveals itself in the manner of a butterfly released from a granite cocoon.

Madrigal, by Fafrd, is such a puzzle. We are given an 11×11 grid, a two-cell cage marked 11 near its foot, an objective, and a short list of rules.1

The general-purpose sudoku website I used to tackle Madrigal wasn’t properly optimised for a problem of this nature, so I’ve provided a board below. Guided mode codifies the structure of the constraints to make it a casual solve of five to ten minutes, while Hard mode, the original puzzle, can take the better part of an hour.

In How to Solve It (1945) the mathematician George Pólya provides a sequence of steps to follow and questions to keep in mind while tackling a mathematical problem.2 I borrowed from that framework while writing up my path to the solution in the sections below.

Only proceed if you’ve either attempted the problem already, or are pressed for time or energy and would like to gain at least the passive insight of seeing how one can orient towards the solution, to be filed away in a dusty cabinet in the cortex (which may serve well, in the scenario that university admissions or job applications develop further into draconian tests of the intellect, veritable gauntlets of fortitude, and you find some day that the only thing that separates you from all that you desire is an unassuming 11×11 grid).

The Data

‘What is the unknown? What are the data? What is the condition?’

The defining feature of this problem, relative to typical sudoku challenges, is the sheer number of unknowns: where the nine boxes go, and what each cell contains. The data provided consist of one cage: two cells whose contents sum to 11. The rest of the rules make up the condition, or the set of constraints.

I started with the simplest aspect. Two cells, containing a single digit each, must sum to 11. There are four pairs of digits that sum to 11: 2 and 9, 3 and 8, 4 and 7, and 5 and 6.

The two cells of the cage touch. Consulting the set of constraints on orthogonally adjacent digits, we find that 5 and 6 cannot be the pair in the cage, since they are consecutive digits. Three pairs remain as candidates, each in either order: six ways to fill the cage.

Neighbours

‘Draw a figure. Introduce suitable notation.’

While I idly snipped away at the lowest-hanging fruit for the problem above, as I often find useful to do as a vague proxy for an athletic warm-up, an idea presented itself. The number of adjacency constraints posed by the last rule might mean that only a handful of possible ways exist to fill up a 3×3 box that does not fail in some way or other. Under the last rule, two digits may not touch if they are consecutive (3 and 4), in a 1:2 ratio (3 and 6), sum to 5 (1 and 4), or sum to 10 (3 and 7). In a little table, I wrote out, for each digit, the digits it may touch. Of the 36 pairs of different digits, I found that only 20 may touch.

Let us call two digits that may touch friends. As depicted in the histogram above, every digit except 4 has at least four friends. The lonesome 4 has just two: 7 and 9.

One Box

‘Could you solve a part of the problem?’

Every 3×3 box contains all nine digits. Inside a box, a corner cell has two neighbours, an edge cell three, and the centre four. 4, as discussed above, has only two friends, so it must sit in a corner, adjacent to a 7 and a 9. I sketched a 3×3 box and gingerly placed a 4 in the bottom-left corner, with 7 above it and 9 to its right; any other corner, or 7 and 9 swapped, would yield the same fundamental box turned or reflected^aaA square has eight symmetries: four turns, counting no turn at all, and four reflections, in its midlines and diagonals. They form the dihedral group of order eight..

The centre touches both 7 and 9, so it must be a friend of each. Apart from 4, only 2 and 5 get along with both. I ruled out 5 by trial and error. Suppose the centre were 5. Then 6 could not sit on an edge, since every edge cell touches the centre and 5 and 6 are consecutive; it would have to be in a corner. That leaves no cell for 2, whose friends are 5, 6, 7 and 9. On a free edge, 2 would touch two corners, and with 7 and 9 already placed, only one of those corners could contain a friend: the 6. In a free corner, 2 would touch two edge cells; with 5 in the centre and 6 off the edges, those would have to be 7 and 9, and the only corner between them is already occupied by the 4.

I imagine this form of social arithmetic is all too familiar to planners of wedding seating arrangements. So far we have found that the centre must be occupied by 2, and its four neighbours are its four friends: 7 and 9, with 5 and 6 on the other two edges. Of those four, 3 may touch only 9 and 5, so 3 takes the bottom-right corner and 5 goes on the right, which puts 6 on top. 8 fits only between 5 and 6, top right, and 1 takes the last corner, between 7 and 6. Ta-da!

Orientations

Every step in building the box was forced by adjacency constraints except the first two: which corner I put the 4 in, and which side of it the 7 went. So there is only one box, ignoring turns and reflections^bbSince the nine digits all differ, no filling looks the same after a turn or reflection, so the 362,880 fillings fall into sets of eight. That makes 45,360 boxes up to symmetry, of which only one passes the last rule. Counting up to symmetry is the subject of a 1937 paper by Pólya.3. It can be turned four ways and each turn reflected, so it comes in eight orientations. I drew the four turns, then mirrored and flipped each: twelve drawings, but only eight distinct boxes, since flipping a box top to bottom has the same result as mirroring its half turn left to right. I did waste some time trying to think up a ninth orientation, suspecting that each of the nine boxes in the grid might need to be distinct, but was eventually satisfied that there were only eight.

In all eight boxes the 2 is in the centre. Along a row of the 11×11 grid, what matters is which three digits a box puts there, not their order. As sets, my original box’s rows are {1, 6, 8}, {2, 5, 7} and {3, 4, 9}. A half turn, a mirror or a flip only reorders them; a quarter turn makes its columns into rows, {1, 4, 7}, {2, 6, 9} and {3, 5, 8}. So the eight orientations fall into two families of four, based on the triples along their rows.

Nine Twos

‘Could you imagine a more accessible related problem?’

Moving from the bounded problem of the box to the open vista of the grid required a change in perspective. I abstracted away the eight peripheral digits (edges and corners) in the box, and focused on the centre. Every box has its 2 in the centre, so the nine 2s mark the arrangement of the boxes on the grid. A box reaches one cell past its centre on every side, so the centres lie in the inner 9×9, rows and columns 2–10. No two centres can share a row or column, or that line would have two 2s. There are nine centres, nine inner rows and nine inner columns, so each inner row and each inner column has exactly one. And no two centres can be within two cells of each other in both directions, or their boxes would overlap.

There are only two answers.^ccIn a square grid two cells wider than the number of boxes, with one centre in each inner row and column, no arrangement exists for two to eight boxes, while there are 40 for 10 boxes and 792 for 11. If the centres need only avoid touching, even at a corner, the question becomes Hertzsprung’s problem: placing kings on a chessboard, one in each row and column, so that none attacks another.4

Of course, the argument is a bit convoluted, since the reasoning behind it in the moment was more spatial than it was deductive. It felt like a kind of square packing problem, where ‘offsets’ were necessary since the ‘cores’ couldn’t line up or there’d be a nuclear meltdown.

The Cage

‘Did you use all the data?’

Only the box centred in row 10 reaches the bottom row. In the mirror image it covers columns 3–5 and leaves both cage cells empty, so the cage cannot sum to 11. The boxes must lie on the staircase, so the cage is the right-hand column of box ix: an edge cell above a corner.

Of the three pairs left at the start, 2 and 9, 3 and 8, and 4 and 7, only 4 and 7 can be an edge cell above a corner, since 2 is always a centre, while 3 and 8 are both corners. So 7 sits above 4 in the cage, with 4 in the bottom-right corner and its other friend, 9, to its left. As in the first box, once 4, 7 and 9 are placed, every other digit has only one possible cell: box ix is my box, mirrored (8 6 1, 5 2 7, 3 9 4).

Families

‘Did you use the whole condition?’

Each of rows 3–9 crosses three boxes^eeA madrigal is a song for several voices. Here the voices are the three boxes crossing each row, as in a round, where each voice sings a different part of the same tune at once. Extended beyond its frame, the grid reads the same after a half turn, so that, like the sheet of a table canon, it can be read from either side of a table.6: the bottom row of the box centred in the row above, the middle row of the box centred in it, and the top row of the box centred in the row below. That is nine cells in one row, so between them they contain all nine digits, once each. A box’s middle row is the one containing its 2. If that row is {2, 5, 7}, only {1, 6, 8} and {3, 4, 9} can complete the nine digits, while if it is {2, 6, 9}, only {1, 4, 7} and {3, 5, 8} can. Either way the three boxes are of one family. The next row down crosses two of the same boxes and one more, which must join their family. Row by row, all nine boxes join box ix’s family, with rows {1, 6, 8}, {2, 5, 7} and {3, 4, 9}. This reduces the number of box orientations we can place in the grid from eight to four.

A box in this family has {1, 6, 8} along its top or bottom row and {3, 4, 9} along the other. In each of rows 3–9, the bottom row of the box above and the top row of the box below must differ. So every box has the same top row, as a set, as the box whose centre is two rows above its own.

By the same argument down columns 3–9, every box has the same left column, as a set, as the box whose centre is two columns to the left of its own. In the staircase a box’s centre row and column are both even or both odd. The five boxes with even centres, i, iii, v, vii and ix, are joined to box ix by steps of two rows and two columns. They share its top row and left column, and only box ix has both, so they are copies of it. Five out of nine boxes dealt with.

By the same steps the four odd boxes, ii, iv, vi and viii, share a top row and a left column, so they are copies of one another. Box viii shows which orientation they take. Box vii’s 4 touches the left end of box viii’s middle row, {2, 5, 7}, and 4 may touch only 7 and 9, so that cell is 7. Two boxes in the family have 7 there: my box, and my box flipped, which is box ix’s half turn. Under box v’s 3 and 9, my box would put 6 and 8, a 1:2 ratio and a consecutive pair. Only the flipped box fits^ffIn the finished grid, neighbouring boxes meet along 24 cell sides. Across these seams the digits are always 1 and 6, 3 and 9, 4 and 7, or 5 and 8, six times each, and each of these pairs is also adjacent inside the box., so the four odd boxes are box ix’s half turn. Fully solved!

The version of the puzzle on SudokuPad, closer to the Hard version above than the Guided one, shipped with a faulty solution checker. Dozens of people had, over the years, hiked up to the very pinnacle of the mountain, paused to admire the view and thought about planting their flag, until the checker told them they were wrong. Frustrated, they trekked over to a YouTube video titled ‘The Greatest Discovery In Sudoku History?’ on the channel Cracking the Cryptic, which features this puzzle, and left comments of relief on seeing that the solution arrived at over the course of an hour-long video matched their own.

Brute Force

‘Can you derive the result differently?’

While writing this piece, two years after solving Madrigal, I asked Claude Opus 5.5 (one of Anthropic’s current flagship AI models) to take a stab at it. I assumed it would manage, given the way thorny mathematical conundrums have been defeated by LLMs lately, but I was still surprised at how quickly it arrived at a solution. It began with one box, checking all 362,880 orderings of the nine digits against the adjacency rule. Eight passed, all the same box turned or reflected. This took under a second.

from itertools import permutations

def may_touch(a, b):
    return not (
        abs(a - b) == 1      # n, n+1
        or a == 2 * b        # 1:2
        or b == 2 * a
        or a + b in (5, 10)  # sums
    )

# cells 0 to 8, read like a page;
# the 12 pairs of side-by-side cells
across = [(i, i + 1) for i in range(9)
          if i % 3 < 2]
down = [(i, i + 3) for i in range(6)]
edges = across + down

digits = range(1, 10)
boxes = [
    p for p in permutations(digits)
    if all(may_touch(p[i], p[j])
           for i, j in edges)
]
print(len(boxes))  # 8

The search tries fillings in dictionary order, so fillings that begin alike sit together in blocks. Of the 72 ways to fill the first two cells, 32 already break a rule, so 44% of all fillings fail at the second cell. A search that stops at the first broken rule visits 2,898 partial boxes, rather than 362,880 whole ones. The first complete box it finds is my box, 1 6 8, 7 2 5, 4 9 3.

Cell by cell Depth first Play Pause Step

123456789

Cell 9 · 312 tried, 8 kept

Digits tried and kept at each cell of the box

Cell	Tried	Kept
1	9	9
2	72	40
3	280	150
4	900	472
5	2,360	568
6	2,272	552
7	1,656	786
8	1,572	312
9	312	8

The search also demonstrates that every part of the last rule is necessary for the box to be unique: if any one of the four adjacency constraints is dropped, between 88 and 2,032 fillings pass.

Once it had the eight boxes, Claude searched the grid. Its program reads the cells in order, like a page. Each cell is either left empty or becomes the top-left corner of a box in one of the eight orientations. A branch is dropped as soon as a digit repeats in a row or column, a forbidden pair touches, or more than 40 cells are empty. The cage’s total is checked once all nine boxes are down.

N = 11

def turn(b):  # a quarter turn
    return [list(r)
            for r in zip(*b[::-1])]

def mirror(b):  # left to right
    return [r[::-1] for r in b]

box = [[1, 6, 8],
       [7, 2, 5],
       [4, 9, 3]]
orients = []
for _ in range(4):
    orients += [box, mirror(box)]
    box = turn(box)

grid = {}     # (row, col): digit
used = set()  # filled or left empty
row = [set() for _ in range(N)]
col = [set() for _ in range(N)]
cage = [(9, 8), (10, 8)]
found = []

def cells(r, c, b):
    return [(r + i, c + j, b[i][j])
            for i in range(3)
            for j in range(3)]

def near(y, x):  # digits beside it
    spots = [(y - 1, x), (y + 1, x),
             (y, x - 1), (y, x + 1)]
    return [grid[s] for s in spots
            if s in grid]

def fits(r, c, b):
    if r + 3 > N or c + 3 > N:
        return False
    for y, x, d in cells(r, c, b):
        if (y, x) in used:
            return False
        if d in row[y] or d in col[x]:
            return False
        for e in near(y, x):
            if not may_touch(d, e):
                return False
    return True

def put(r, c, b):
    for y, x, d in cells(r, c, b):
        grid[y, x] = d
        used.add((y, x))
        row[y].add(d)
        col[x].add(d)

def take(r, c, b):
    for y, x, d in cells(r, c, b):
        del grid[y, x]
        used.remove((y, x))
        row[y].remove(d)
        col[x].remove(d)

# i: the next cell, read like a page;
# n: boxes placed;
# gaps: cells left empty
def search(i, n, gaps):
    if n == 9:
        total = sum(grid.get(s, 0)
                    for s in cage)
        if total == 11:
            found.append(dict(grid))
        return
    if gaps > 40:
        return
    while divmod(i, N) in used:
        i += 1
    if i == N * N:
        return
    y, x = divmod(i, N)
    for b in orients:
        if not fits(y, x, b):
            continue
        put(y, x, b)
        search(i + 1, n + 1, gaps)
        take(y, x, b)
    if (y, x) not in cage:
        used.add((y, x))
        search(i + 1, n, gaps + 1)
        used.remove((y, x))

search(0, 0, 0)
print(len(found))  # 1

In 90 seconds it visited about 8 million partial grids. In 92% of them the first box’s centre was in row 2. Only 16 reached nine boxes. Each alternates one box with its half turn, on the staircase or its mirror image. The cage sums to 11 in one arrangement, which the search found about a quarter of the way through. The remaining three quarters of the search established that there was no other satisfactory solution.

Of its dead ends, 99.94% had more than 40 empty cells. A finished grid has exactly 40.

Only after finding the solution did it look for reasons, working back from the answer to an argument and checking each step by computation. I hope the extended digression into how our silicon successors tackle problems, seemingly superhuman yet also remarkably pedestrian, was fruitful for readers interested in the state of the art.

Although my (our?) solution may in contrast appear to have been arrived at more elegantly, moving forward from first principles, I think a very firm assumption that the solution existed, and that the given rules were sufficient to reach it, was key to the process. Pólya has an entry on working backwards, which he traces to Pappus of Alexandria: assume that what is sought has been found, and ask what it could have come from.7 A useful approach to puzzles, and to life.