Picture Logic Puzzle Maker

A picture logic puzzle, often called a nonogram, hands you an empty grid with numbers down one side and across the top. Fill the right cells and a picture appears. No word of any language is needed, which goes some way to explaining how far the puzzle has travelled, and teachers have used it to train logical thinking.

It also looks like a puzzle that cannot go wrong. The numbers were counted from a picture, so the picture must fit them. It does. The trouble is that another picture may fit them too, and a solver who meets that fork can only guess. Making such a puzzle is easy. Making a fair one is a different job.

Lit windows in Tokyo, a name from Britain

The puzzle has two inventors who did not know about each other. In 1987 Non Ishida, a Japanese graphics editor, won a competition in Tokyo by designing grid pictures using skyscraper lights that were turned on or off. At the same time, and with no connection, a professional puzzler named Tetsuya Nishio invented the same thing. The following year Ishida published three of her picture grids as Window Art Puzzles, while Nishio called his Oekaki-Logic, which means picture logic or drawing logic.

The best known English name came from a collector. In 1990 James Dalgety of The Puzzle Museum in the United Kingdom invented the name Nonograms after Non Ishida, and The Sunday Telegraph began to print the puzzles every week. In 1998 the paper asked readers to choose a new name and Griddlers won. Other publishers and programmers added more, Paint by Numbers among them, and the puzzle now lives under a crowd of titles. The author of one well known free puzzle collection recalls first meeting it around 1995 as nonograms.

How the numbers work

The rule fits in a sentence. Beside each row and above each column are the lengths, in order, of the runs of filled cells in that line, and two runs are always separated by at least one empty cell. A clue of 3 1 means a run of three, a gap of any size from one cell up, then a single cell. Empty cells may also sit before the first run and after the last. Researchers at Leiden write the same thing as a pattern: any number of empties, the first run, one or more empties, the next run, and so on to the end.

Colored versions of the puzzle exist and change the rule, because two runs of different colors may touch with no gap between them. Everything here is about the two-color kind.

Solving starts with a single line. A widely read beginners’ guide says solving always starts with the longest runs, and the reason is the overlap. Take the Sailboat picture built into the tool above, a grid ten cells wide. Row 7 has the clue 10, so all ten cells are filled. Row 8 has the clue 8. Pushed hard left the run covers cells 1 to 8, pushed hard right it covers cells 3 to 10, and the cells both positions share, 3 to 8, are filled whatever else is true. Row 9 has the clue 6, and by the same sum only cells 5 and 6 are certain.

Those are the first three hints the tool gives on that puzzle. From there the columns take over. A column whose clue is 1 and which already holds a filled cell is finished, so every other cell in it is marked empty. Marking empties matters as much as filling: a cell no run can reach is information, and it is often what lets the next line move. The Sailboat needs three sweeps in all, rows, then columns, then rows again.

Programs do the same thing. The common method, as the author of one validator describes it, finds the placement with every run pushed left, the placement with every run pushed right, and keeps what the two agree on. He adds that it is fast, but not complete. The complete version asks a stricter question. Of all the ways to finish this line that respect the marks already made, which cells come out the same every time? The Leiden authors call that operation settling, compute it by dynamic programming without listing the arrangements, and give an example: a line of eleven cells marked ?1?1?0????? with the clue 3 2 1 settles to 011100?1???.

One picture, or several

Designers always work from the picture to the clues, never the other way, and not every picture makes a good puzzle. The smallest bad one has 4 cells. Fill two opposite corners of a two by two block. Each row has the clue 1 and so does each column. Now fill the other two corners instead: the clues are identical. The Leiden papers call this an elementary switching component, four cells, two filled and two empty, that can be swapped without changing any clue. Draw it in the tool and all four cells are ringed.

The same trap hides inside larger pictures, where it is harder to see. When a puzzle is nearly determined, the leftover doubtful cells come at least two to a line, so there are never fewer than four of them and never exactly five. Whether a rectangle of four really switches depends on its neighbors as well, on the cells along its sides and beside its corners. Two lone dots on a diagonal in open space are the plainest example, and enough to spoil an otherwise sound drawing.

One solution is necessary for fairness and still not enough. A puzzle can have a single answer that no chain of single-line reasoning reaches, so the solver must suppose a cell is filled and follow the consequences until something breaks. The Leiden authors reserve the word simple for puzzles that line reasoning alone finishes, and note that puzzle books are filled almost entirely with that kind. When line solving succeeds it proves two things at once: the answer is unique, and a person can find it without guessing.

How common is the fair kind? For five by five grids the question has been answered by checking every one of the 33,554,432 possible pictures. Of those, 25,309,575 have clues that allow one answer only, and 24,976,511, which is 74.44% of all pictures, are simple. Roughly one small picture in four, drawn at random, is not a fair puzzle. The same study counts the alternating sweeps over rows and columns that each simple puzzle needs and uses that count as its difficulty. The hardest five by five takes 17.

Why a computer cannot just grind it out

It would be convenient if a program could always settle the matter. In general it cannot do so quickly. Deciding whether a set of clues has any solution at all is NP-complete, a result first proved by Ueda and Nagao in a 1996 technical report and later re-derived with a general toolkit for puzzle hardness. Their report shows as well that being handed one solution does not make it easy to decide whether a second exists. The general problem is hard in the formal sense, even though the puzzles in books are solved by hand.

Yet people solve these for pleasure, and the reason is that puzzles made for people sit far from the hard cases. Recent experiments tie the difficulty of finding the next forced cell mostly to one number, the share of cells that are filled. The Leiden authors saw the same thing from the other side: as the share of filled cells changes gradually, puzzles flip abruptly between easy ones and very hard ones that often have many answers.

So an honest puzzle checker has limits and should say so. Line logic gives a proof when it finishes and nothing when it stalls. A search for a second answer can run out of time on a large, noisy grid, and the right report then is that the question is undecided. A sweep count is also not a measure of how hard a person will find a puzzle; the study that defines it leaves that link to future work.

Drawing pictures that make good puzzles

The tempting shortcut is to take a photograph, turn every dark pixel into a filled cell and call it done. The people who built an automatic generator report that simple thresholding of a gray picture usually does not give a puzzle that can be solved by hand: either it has more than one answer or it needs trial and error. A converted photograph is a first sketch.

Their repair is worth copying. Run line logic until it stalls, look at the cells it could not decide, fill one of the empty ones, and try again. The loop always ends, because a grid that is entirely filled is certainly solvable. Adding ink in the doubtful region is the dependable fix, and the tool above offers it as a suggestion: the cell, or the few cells, whose change lets line logic finish.

Give the solver somewhere to start. A run longer than half its line guarantees an overlap, and a full line or an empty one is a gift. A drawing made only of short strokes may offer no first move at all.

Then test, adjust and test again, which is the routine one puzzle site built its validator to shorten. Remember also that solvers cheat in a way no proof sees: they recognize the picture and fill in what a boat or a face ought to have. A puzzle of random cells cannot be guessed that way, which a user of one puzzle collection counted in its favor. A drawn puzzle should hold up without the help.

Since the clues are the whole puzzle, they can be saved as nothing more than a short text file: the width, the height, then one line of numbers for each row and each column. Everything a solver will ever know is in that file. The picture is fair only if it is in there too, complete, with no second reading. Clues are a compression of a picture, and the craft is making sure nothing was lost.