Draft: very much under construction.

Draft · Reverse Game of Life Font

Reverse Game of Life Font

What is Conway's Game of Life?

Quick FAQ explainer. As simple and as visual as possible: the game and the rules are clear.

Our own interactive demo, or link to other people's demos?

Draft labels below are placeholders for your wording.

Every cell updates at the same time, using its neighbors from the step before.

Step 0

Click or drag to draw cells, then press Step or Play.

Summary: the whole game is these few simple rules, applied to every square, one step at a time.

Check	Action
Dead, with exactly 3 live neighbors	Comes alive
Alive, with fewer than 2 live neighbors	Dies
Alive, with 2 or 3 live neighbors	Stays alive
Alive, with more than 3 live neighbors	Dies

The question: can we run it backward?

Visual explanation of the question: find starter seeds that make any arbitrary image or pattern.

Original idea: a pixel board you draw on; the algorithm chugs and finds an N-step-back seed (exists in MATLAB: reverseGameOfLife.m).
Could it work for any black-and-white image?

Draft labels below are placeholders for your wording.

Five patterns on a 5 × 5 grid with wrap-around edges. A computer can try all 33,554,432 possible starting patterns, so these counts are exact.

Draw a target

Grid Steps back

Draw a pattern, then press Find seeds.

Edges wrap around. Each row shows one seed found and the steps it takes to reach your target.

How the search works

The obvious way is to try every possible seed and see which ones turn into your target. On a 6 × 6 grid that is 2³⁶, about 69 billion seeds: too many for a web page.

The trick is that each row of the target depends on only three rows of the seed: the same row, the one above, and the one below. So the search builds the seed one row at a time:

Before searching, it works out what every possible stack of three rows turns into. On a 6-wide grid that is 2¹⁸ = 262,144 stacks, done once.
It picks the seed's first two rows (4,096 choices, tried one after another).
For each next row, it only tries rows that make the row above come out right in the target. Usually that leaves just a few options, and often none, so dead ends are dropped right away.
When all six rows are placed, it checks the last two target rows, which wrap around to the top.

Because no possibility is skipped, the count is exact when the search finishes, and "no seed exists" is a proof, not a guess.

For more steps back, it repeats the same search from every seed it found: seeds of seeds. The number of branches can explode, so the search stops after 4 seconds and reports what it found so far.

Why one or two steps back isn't enough

1- or 2-step seeds seemed a bit underwhelming. The fun is going back far enough that you really can't see or guess the final outcome.

VISUAL [TBD]

So: make a font

That leads to the idea of making a font.

VISUAL [TBD]

The search: getting N steps back

Show the work, with as many images along the way as we can. Visual explainers of the search algorithms. How and why it gets super hard.

Draft labels below are placeholders for your wording. Images are the original MATLAB figures, in place as placeholders; order and selection TBD.

Local search: genetic algorithm + simulated annealing

Genetic algorithm: 300 random seeds; score = wrong pixels after N steps; keep the best 30, breed the rest (mix two parents cell by cell, flip ~3% of cells); ~400 generations.
It gets letters to ~7–10 wrong pixels, then stalls: by ~generation 200 the seeds are near-copies of each other. Works best as a starting point.
Simulated annealing polishes the GA's best seed: flip 1–2 cells, keep improvements, sometimes keep worse moves (the "temperature"), cooling over time. Does most of the real work: 7–10 → 0–4 wrong pixels.
Results: 93/94 exact at 1 step, 70/94 at 2, 35/94 at 3.
Side experiment: chaining two 1-step solves to get a 2-step seed failed (1/94 exact).

VISUAL: small animated explainer of GA (population, breeding) + SA (flip, accept/reject, cooling) [TBD]

Hitting the wall

Tested every change of 1, 2, 3 and 4 cells around the best seeds: none improved. Stuck in a dip at least 5 flips deep.
Ten fresh restarts found very different seeds with the same error count, so it looked like a hard floor.
Show: the E key view below and the old 3-step catalog (30/94 at the time, with error pixels).

correctmissing (should be on) extra (should be off)

How to read the catalogs: the letter E, 3 steps back. Top: the best seed local search (GA + SA) found grows into an E with 4 wrong pixels, labeled "e4" in the catalogs. Bottom: the SAT solver's seed grows into the exact E (found in 1,503 seconds).

Catalog of 10 by 10 seeds for every character — The 1-step seeds: plant one, run one step, get the letter.

Catalog of letters grown from 1-step seeds — 1 step back, local search: 90 of 94 exact at the time (now 94 of 94).

Catalog of letters grown from 2-step seeds — 2 steps back, local search: 70 of 94 exact. The SAT solver later got all 94.

Catalog of letters grown from 3-step seeds — 3 steps back, local search: 30 of 94 exact in this figure. The SAT solver later got all 94.

SAT solving: turn it into a logic puzzle (Z3)

Stop guessing: one true/false variable per cell per step (N+1 layers of 10 × 10). The Life rule becomes a logical constraint on every cell; the last layer is fixed to the letter.
The solver answers one of three ways: here's an exact seed / impossible (a proof: Garden of Eden) / out of time.
Z3: general-purpose solver from Microsoft Research.
Result: exact seeds for every letter local search couldn't solve. 2 steps and 3 steps both 94/94. The "hard floor" was local search getting stuck, not the problem. Hardest: & at 3 steps, 40 minutes.

VISUAL: the layers (seed → step 1 → … → letter) with one cell's rule drawn as a constraint [TBD]

Kissat: a specialist solver

Z3 handles many kinds of problems; this one is purely true/false, which dedicated SAT solvers are built for. Kissat is one of the top solvers in the annual SAT competitions (used through the PySAT library).
Rules rewritten in the standard clause format with my own neighbor-counting encoding. The ready-made one in PySAT gave false "solved" answers (half-built: treated 3 neighbors as 4); mine was tested for every count 0–8.
About 40–50× faster on the same problems (&: 2,401 s → 48 s). Made 4 steps practical.
4 steps back: 94/94 exact (finished 2026-10-17). Most letters 10 s – 7 min; the hardest: E 30 min, 3 12 min, h 10 min.

VISUAL: Z3 vs Kissat time for the same letters; 4-step catalog [TBD]

Why it gets harder

Draft. Possible order: more squares → more steps → the edges. Could also move up into section 2. The solve-time chart is Z3 only (1–3 steps); could add the 4-step Kissat times.

Possible seeds for each grid size

Every extra square doubles the count: an n × n grid has 2^n×n. Hover a bar for details.

Checking a billion seeds per second, 6 × 6 takes about 69 seconds; 10 × 10 (the font) would take about 40 trillion years.

Patterns that can be reached, by steps back

5 × 5 grid with wrap-around edges, all 33,554,432 patterns checked (exact).

Only a quarter of all patterns have any seed one step back; by six steps, 3%.

Letters solved exactly, by steps back

The 94-character font on a 10 × 10 grid.

local search alone (GA + SA)with the SAT solver

SAT solve time per letter, by steps back

Median seconds, log scale. Z3 engine, run on the letters local search couldn't solve.

Each step back multiplied the time by about 20 to 65 times. (The later Kissat engine is about 40 to 50 times faster, which is what made 4 steps possible.)

Wrap-around edges. The grid has no edge: a cell on the border counts neighbors on the opposite side, like a world map that wraps.

Tight: 8 × 8. The letter on its own 8 × 8 grid, with no room around it.

Padded: 10 × 10. The same 8 × 8 letter with an empty border around it.

A bigger grid was easier

Exact letters with local search (GA + SA). The padded grid has far more possible seeds, but the empty border gives the pattern room to move.

tight 8 × 8padded 10 × 10

Gardens of Eden: the impossible patterns

Gardens of Eden, or impossible things. Harder to find or prove, maybe.

VISUAL [TBD]

Type with it

Not just the list of seeds: the interactive demo for typing in the N-steps-back Game of Life fonts. Maybe a downloadable font package.

Type anything, then press Play. Open the typer on its own page ↗

DOWNLOAD: font package [idea]