Nonogram generator in Python: half of random grids have two answers

A nonogram, also sold as griddlers or picross, gives you the lengths of the runs of filled squares in every row and column, and you work out the picture. Making the clues is easy: draw a grid, count the runs. Whether those clues make a fair puzzle is a different question, and a quick generator never asks it.

Two things can go wrong. The clues can fit more than one grid, so the solver finishes a picture that is not the one in your answers. Or they fit one grid, but only someone who guesses and backtracks will get there. On 30 October 2026 we measured both on random grids, with the code below.

The short version#

• 10 x 10, half the squares filled: 50% of 400 random grids had exactly one answer, and 46% could be finished by line logic alone.
• 10 x 10, 60% filled: 84% one answer, 84% by line logic.
• 15 x 15, half filled: 24% one answer, 20% by line logic. 60% filled: 76% and 74%.
• The fix is a filter: draw a grid, solve it from its clues by line logic, keep it only if that finishes. At 10 x 10 and 60% filled that took 1.1 random grids per puzzle on average, about 1 ms each; at 15 x 15 about 6 ms.

The code#

from functools import lru_cache
import random


def clues(line):
    """Lengths of the runs of filled squares: [1, 1, 0, 1, 1, 1] -> (2, 3)."""
    out, run = [], 0
    for v in list(line) + [0]:
        if v:
            run += 1
        elif run:
            out.append(run)
            run = 0
    return tuple(out)


@lru_cache(maxsize=None)
def options(clue, n):
    """Every way to lay out the runs of `clue` in a line of n squares, as tuples of 0 and 1."""
    if not clue:
        return [(0,) * n]
    first, rest = clue[0], clue[1:]
    need = sum(rest) + len(rest)                   # room the other runs take, with a gap before each
    out = []
    for start in range(n - need - first + 1):
        head = (0,) * start + (1,) * first
        if rest:
            out += [head + (0,) + tail for tail in options(rest, n - len(head) - 1)]
        else:
            out.append(head + (0,) * (n - len(head)))
    return out


def solve(rows, cols, grid=None):
    """Line logic: in each row and column keep the layouts that agree with the known squares, and fill every square
    on which all of them agree; repeat until nothing changes. Returns the grid (None = unknown) or False on a clash."""
    h, w = len(rows), len(cols)
    grid = [r[:] for r in grid] if grid else [[None] * w for _ in range(h)]
    lines = [('r', i, rows[i], w) for i in range(h)] + [('c', j, cols[j], h) for j in range(w)]
    changed = True
    while changed:
        changed = False
        for kind, i, clue, n in lines:
            known = grid[i] if kind == 'r' else [grid[y][i] for y in range(h)]
            fits = [o for o in options(clue, n) if all(k is None or k == v for k, v in zip(known, o))]
            if not fits:
                return False
            for k in range(n):
                if known[k] is None and all(o[k] == fits[0][k] for o in fits):
                    y, x = (i, k) if kind == 'r' else (k, i)
                    grid[y][x] = fits[0][k]
                    changed = True
    return grid


def count_answers(rows, cols, grid=None, stop=2):
    """How many grids fit the clues (stops counting at `stop`): line logic, then a guess where it gets stuck."""
    grid = solve(rows, cols, grid)
    if grid is False:
        return 0
    for y, row in enumerate(grid):
        for x, v in enumerate(row):
            if v is None:
                total = 0
                for guess in (1, 0):
                    grid[y][x] = guess
                    total += count_answers(rows, cols, grid, stop - total)
                    if total >= stop:
                        break
                return total
    return 1


def make(h, w, fill=0.5, rng=random, tries=1000):
    """A random picture whose clues a solver can finish with line logic alone (so it also has exactly one answer)."""
    for n in range(1, tries + 1):
        grid = [[int(rng.random() < fill) for _ in range(w)] for _ in range(h)]
        rows = [clues(r) for r in grid]
        cols = [clues(c) for c in zip(*grid)]
        result = solve(rows, cols)
        if result and all(v is not None for r in result for v in r):
            return grid, rows, cols, n
    raise RuntimeError("no puzzle a solver can finish by logic")

grid, rows, cols, tries = make(10, 10, fill=0.6, rng=random.Random(5))
print("rows:", rows)
print("cols:", cols)
print("random grids tried:", tries, "| answers:", count_answers(rows, cols))
print("\n".join("".join("#" if v else "." for v in r) for r in grid))

With that seed the first random grid already passed: one answer, finished by line logic.

Line logic, the way a solver works#

For one row with clue (2, 3) in 10 squares there are only so many ways to lay out a run of 2 and a run of 3 with a gap between them. options() lists them. solve() keeps, for every row and column, the layouts that agree with the squares already known, and fills every square on which all of them agree. Then it goes round again, because each filled square narrows the crossing column, until nothing changes.

That is what a person does with a pencil, so a grid that solve() finishes is one a solver can finish without guessing. It also has exactly one answer: every square it filled was the only possible value. In our runs it never filled a square differently from the original grid.

Counting answers#

When line logic gets stuck, count_answers() guesses one square, both ways, solves on from each and counts the grids that fit, stopping at 2. We used it only to measure how many random grids have one answer; a book does not need it, because make() keeps only the grids line logic finishes.

The gap between the two numbers is small but real. At 15 x 15 and half filled, 24% had one answer, but only 20% could be finished without a guess. Those 4% are the puzzles readers call unfair.

Why the fill matters#

A grid that is half filled has many short runs, and short runs leave lines with many possible layouts, so line logic has little to go on. At 60% the runs are longer and the lines lock in faster: the share of fair grids rose from 50% to 84% at 10 x 10, and the median time to solve fell from 3 ms to 1 ms.

A random grid is noise, though, not a picture. Books use pictures, and a picture's clues can fit two grids too, so the same two checks apply to every picture before it is printed.

A whole book, not one grid#

Our nonogram book maker makes those checks on every puzzle: a separate counter confirms each grid has exactly one solution, and each puzzle is solved again line by line, with no guessing, after it is made and again before it is printed. Every grid hides a real picture (animals, food, vehicles, tools and more, picked by hand), no row or column has more than 5 numbers, and the answers at the back are named. Easy books use 15 x 15 grids, medium 20 x 20 and hard 25 x 25, and the book is checked against KDP's paperback specs before you can download it. One nonogram book costs 500 credits, from $3.30 in the big pack.