The mathematics of Cell Blocks

Cell Blocks is a grid of numbers you cut into rectangles. Each rectangle holds exactly one number, and that number is its area. There is nothing else to it, and a good one takes about four minutes.

The interesting part is not solving it. It is that the solver you write for it is a general machine, an exact cover, and that the obvious harder variants each break a different piece of that machine. Which piece breaks tells you what to build next. That correspondence is unusually clean here, and it is what this post is about.

Names

Nikoli, the Japanese publisher that put most of these puzzles into circulation, calls it Shikaku and subtitles it “Divide by Box”. Elsewhere it appears as Cell Blocks, Divide by Squares or just Rectangles. I use Cell Blocks for the thing I built, because it also plays Fillomino, and Shikaku for the specific Nikoli ruleset. Where the distinction matters below I say which I mean.

The rules, and a board

A grid. A set of clues, each a cell and a positive integer , with

Find a partition of the grid into axis-aligned rectangles such that each rectangle contains exactly one clue, and its area equals that clue.

SHIKAKU · UNIQUE SOLUTION

Cell Blocks

RECTANGLESPOLYOMINOES

Drag to draw rectangles. Each block holds exactly one number — its area. Tap a block to remove it.

constructing a layout…

EASY 6×6MEDIUM 8×8HARD 10×10

NEW PUZZLESHOW SOLUTIONCLEAR

A published puzzle has exactly one solution. That is not editorial fussiness. Players use it as a reasoning tool (if this placement leaves an ambiguous 2×2 somewhere else, it cannot be right), so a puzzle with two solutions is not merely untidy; it invalidates a technique the reader is entitled to use. It also means the generator has to prove uniqueness before it prints anything, which turns out to be the expensive half of the whole exercise.

The full-page version, with Fillomino as well, is at /games/cell-blocks/.

What a clue actually says

A clue can only be a rectangle where . So the shape family of a clue is the set of divisor pairs of its value. A prime clue is almost mute: 7 admits only and , two thin strips. A highly composite clue like 24 admits eight orientations before you have placed anything at all.

For a fixed shape, the placements containing the clue cell number at most , since the clue can sit in any cell of its own rectangle, clipped by the grid edges and by other clues, since no rectangle may swallow a second number. That gives an upper bound on candidates per clue of

where is the divisor-count function. This is the main difficulty dial for the base game, and it is worth pausing on the factor, because it is the strange one. The bound is linear in , so bigger clues do cost more: a 13 has 26 candidates against a 6’s 24. But swings much harder than does over the range of values a puzzle actually uses. A grid of primes is almost self-solving; the same grid with every 7 replaced by 8 becomes hard, and 8 is barely larger. Number theory leaks into a puzzle that never mentions it.

The ladder

The solver runs propagation rules to fixpoint, cheapest first. Three of them carry almost everything:

1. Naked single. A clue with one surviving candidate takes it. Commit the rectangle; delete every other clue’s candidates that overlap it.
2. Forced cell. If every remaining candidate of clue covers cell , then belongs to , so delete every other clue’s candidates covering . This is the workhorse; most published puzzles are chains of 1 and 2.
3. Orphan cell. Every cell must be covered by someone. If cell appears only in the candidates of clue , then must cover , so delete ‘s candidates that miss it. The dual of rule 2.

Underneath all three sits a contradiction check rather than a rule: a clue with no candidates left means the position is already lost. And above them sits the fourth tier, which is not a rule at all: when the three stall, the solver has to guess, and a board that reaches this tier is one no chain of deductions will open.

Rules 2 and 3 are worth reading together, because they are the same observation from opposite ends. Rule 2 reasons from a clue’s options to a cell’s owner; rule 3 reasons from a cell’s options to a clue’s obligation. Exact cover problems tend to come in dual pairs like this, and noticing it saves you writing the second rule from scratch.

The ladder is not only a solver. Each tier is a difficulty grade, and the deepest tier a puzzle actually requires is what the generator stamps on it. A board solvable by rules 1 and 2 alone is easy; one that forces rule 3, harder; one that reaches tier IV, unpublishable. That grades a puzzle by naming the hardest thing a solver is obliged to do, rather than by size or clue count.

The same problem, as exact cover

The whole thing maps onto exact cover, and from there onto Donald Knuth’s Dancing Links. Columns are constraints to satisfy exactly once: one per cell (it must be covered) and one per clue (it must be used). Rows are candidate rectangles, each covering its own cells’ columns plus its clue’s column. Find a set of rows hitting every column exactly once and you have a solution.

Mr Knuth’s own worked example of Algorithm X was tiling a tray with polyominoes, so this is less a translation than a homecoming.

Being precise about what that buys, since it is easy to oversell: Dancing Links picks the column with the fewest rows and detects a column with none, so it gets rule 1 and the contradiction check for free. It does not get rules 2 and 3. “Every remaining candidate of this clue covers cell ” is an inference DLX never draws; it would simply branch instead. What DLX gives you is a fast, correct enumerator, which is what a uniqueness oracle needs.

So the ladder earns its keep for a different reason: DLX can tell you that a puzzle has one solution and nothing about how a person would find it. The ladder grades human difficulty; the enumerator certifies correctness. They answer different questions and neither replaces the other. (What actually ships here is a plainer backtracker with the same min-candidates branching rule rather than Knuth’s linked-list machinery; at these board sizes the constant factor was not worth the code.)

Uniqueness is counting, and counting is the expensive part

Verifying uniqueness means not stopping at the first solution: you keep going until a second appears or the search exhausts. There is no shortcut past this. And having one solution already in hand does not make finding the next one any easier. For several Nikoli puzzles, provably not. In 2003 Takayuki Yato and Takahiro Seta generalised the Another Solution Problem, introduced by Nobuhisa Ueda and Tadaaki Nagao in 1996, and proved it complete for Slither Link, Cross Sum and Sudoku, tying that hardness directly to the difficulty of designing puzzles. Note what is and is not claimed: both problems are NP-complete, so this is not a separation. It is the stronger-sounding and more useful statement that the free head start a generator has (it built the solution itself) buys it nothing.

Which is exactly the position a generator is in. It cannot check uniqueness cheaply, so it must make the search cheap instead: propagate hard at every node, branch on the clue with the fewest candidates, and cap the work with a node budget so a pathological board reports “I could not decide” rather than hanging. A budget that runs out is not evidence of uniqueness, and the generator has to treat it as a veto rather than a pass. That is the one place where an off-by-one in your scepticism ships a broken puzzle.

Three assumptions, and the variants that break them

Here is the part that makes the base solver worth designing carefully. It leans on exactly three assumptions:

• A. Candidates are enumerable. Each clue has a small, listable set of possible shapes, computable up front.
• B. Areas sum exactly. holds as an equality, so any arithmetic on remaining area is exact.
• C. Every block is anchored. Each block contains exactly one clue, so blocks and clues are in bijection.

Every harder variant I can think of has a first break among these, the one assumption whose failure forces the representation to change, and the machinery you need follows from which one it is. Several variants go on to break a second assumption, and where they do, the second break is the cheap one: it costs an extra bookkeeping rule, not a new way of describing the problem. Sorting variants by their first break is what makes the list below useful rather than merely tidy.

Nothing in what follows is shipped code. The base solver is real; these are sketches of what each variant would demand of it, which is the point of running the exercise.

Nastier instances break nothing

Composite-heavy clues, clues placed centrally rather than at corners, a torus grid with no edges. Nothing breaks logically; candidate sets simply balloon. On a torus, edge clipping vanishes and clues come much closer to the full bound. Coordinates become modular, and bitmasks still work unchanged. Not all the way, though, and the exception is a nice one: a shape as wide as the grid wraps onto itself, so all horizontal offsets cover the same cells and the whole family collapses to a single placement. The clues that lose most are exactly the composite-heavy ones this variant was meant to punish.

The extension is engineering, not logic: incremental propagation queues so you only re-examine clues whose candidate sets changed, memoised fixpoints along search branches, and bitset-parallel rule 2 and 3 checks: AND together all of a clue’s candidates in one pass and you have its forced-cell mask for free.

Perimeter clues break B

Suppose the clue gives the perimeter: . Odd is simply impossible; for even the shape family is linear, since , so enumeration survives. But area now varies across candidates, and the global equality degrades to an interval. Writing and for a clue’s smallest and largest surviving area:

The extension is interval propagation. Each clue carries its range over live candidates; whenever a range tightens, re-check the global sum and each connected uncovered region. Region-local sums matter too, and they need stating carefully, because the tempting version is wrong. Clues confined to an uncovered region (every candidate inside it) do not have to fill between them, since a clue with candidates both inside and outside may still land inside. So the sound pair of bounds is one-sided at each end: the confined clues’ minimum areas sum to at most , and the maximum areas of every clue that can reach sum to at least .

Candidate generation itself is a one-line change. The exact-cover core is untouched, because the cover is still exact: you have only lost a pruning invariant and must replace it with bounds. The same treatment handles clues that give one dimension and leave the other free, and inequality clues of the form “area at least ”.

Unclued blocks break C

Let blocks carry no number. The cover now has anonymous rows. The naive fix (add every possible rectangle as an anonymous candidate, with a global counter requiring exactly of them) is correct and explodes immediately. (This variant breaks B in passing too: the printed numbers no longer sum to , they sum to minus whatever the anonymous blocks take. But that is an accounting change, not a representation change, which is why C is the break that matters.)

The workable version runs the clued solver as far as it goes and treats the residue as a set of rectilinear holes to be partitioned into exactly clue-free rectangles between them. Then it adds a feasibility propagator using the classic minimum-partition result: a rectilinear polygon needs rectangles, where counts concave corners, is the largest set of independent chords joining them, and is the number of holes. The hole term earns its place here: the residue left by placed rectangles is exactly the kind of region that encloses one. If the holes need more rectangles than you have left, backtrack. And branch on holes rather than clues: pick a corner cell of a hole and enumerate the maximal rectangles covering it.

Non-rectangular blocks break A

Allow L-shapes, then arbitrary polyominoes, and candidate enumeration dies. The number of fixed polyominoes of size grows like , where . You cannot list the candidates for a clue of 12.

It is worth being precise about what anyone has actually proved here, because this is a nice example of how much of a familiar constant is conjecture. That the limit exists follows from supermultiplicativity, plus Fekete’s lemma. (Glue any -omino to any -omino and you get a distinct -omino, so .) David Klarner and Ronald Rivest gave the upper bound in 1973, since improved to by Gill Barequet and Mira Shalah; Barequet, Günter Rote and Shalah proved the lower bound in 2016. The value 4.06 itself, and the finer asymptotic , are conjecture backed by numerical evidence rather than proof. None of that weakens the argument: at 4.06 rather than the 3.7 I first wrote down, enumeration dies faster.

So the representation has to change: from candidate lists to region growing. Each clue seeds a region, and for every empty cell you maintain the set of clues that could still absorb it, computed by bounded flood fill: cell is reachable by clue only if a path from to shorter than exists through cells not owned by other regions.

The propagators become graph rules, and the family resemblance to the originals is striking:

• Unique reacher, the analogue of the orphan cell: if only one clue can reach , it takes , though now joining requires checking the region can still connect to with enough budget left.
• Articulation forcing, the analogue of the forced cell: if every way for a region to reach its required size passes through cell , commit . This is a min-cut or articulation-point test on the reachability subgraph.
• Pocket accounting: an enclosed empty pocket must be exactly fillable by the regions bordering it.

Fillomino adds rules of its own on top, and in doing so breaks C as thoroughly as A: several clues of equal value may share one region, so clues and blocks are no longer in bijection, and unclued regions are permitted, which drags in the whole unclued-blocks apparatus with polyomino holes instead of rectangular ones. B goes as well, since the printed numbers now double-count: three 5s in one region contribute 15 to the sum and 5 to the board. It still belongs under A, because A is the break that forces region growing; the other two are handled by rules written on top of that representation. There is also a genuinely new constraint with no analogue above: two completed regions of equal size may not be orthogonally adjacent, since they would merge into one region of the wrong size.

Exact cover stops being the right skeleton at this point. You can write the propagators bespoke, which is the enjoyable route, or compile the thing to CP-SAT with owner[cell] variables, counting constraints for sizes and a standard flow encoding for connectivity. But note what you lose either way: SAT tells you nothing about which human technique a puzzle demands, so the bespoke ladder still has to exist if you want to grade difficulty.

The variants at a glance

What this buys you

Three layers, kept apart:

1. The shape model answers “what could this clue’s block still be?” It is a static list, then a lazy predicate family, then a reachability structure.
2. The propagator set is rules over that model, each tagged with a human-difficulty tier.
3. Search and the uniqueness oracle branch over whatever the shape model exposes.

Keep them separate and the generator needs no variant-specific logic at all: partition, place clues, grade, hill-climb towards a target difficulty while the oracle confirms uniqueness. Swap layers 1 and 2 and the same generator produces a different puzzle.

That is the actual payoff of noticing which assumption a variant breaks first. It is not that the classification is elegant; it is a bit leaky, as the table’s second column admits. It is that a solver designed around three named assumptions has three named seams, so a variant arrives as a change to one layer rather than a rewrite.

Sources

• Donald E. Knuth, “Dancing Links”, Millennial Perspectives in Computer Science, 2000. arXiv:cs/0011047
• Takayuki Yato and Takahiro Seta, “Complexity and Completeness of Finding Another Solution and Its Application to Puzzles”, IEICE Transactions on Fundamentals E86-A(5), 2003. The Another Solution Problem itself is due to Nobuhisa Ueda and Tadaaki Nagao, “NP-completeness results for NONOGRAM via parsimonious reductions”, 1996.
• Gill Barequet, Günter Rote and Mira Shalah, “λ > 4: An Improved Lower Bound on the Growth Constant of Polyominoes”, Communications of the ACM 59(7), 2016.
• David A. Klarner and Ronald L. Rivest, “A procedure for improving the upper bound for the number of n-ominoes”, Canadian Journal of Mathematics 25, 1973. The λ ≤ 4.6496 bound, since improved to 4.5252 by Barequet and Shalah, “Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes” (arXiv:1906.11447).
• D. H. Redelmeier, “Counting polyominoes: Yet another attack”, Discrete Mathematics 36, 1981.
• OEIS A001168, fixed polyominoes.
• Nikoli’s own rules for Shikaku and Fillomino.