Paint-and-place logic puzzles

Nonogram, Bulb Placement and Mine Logic. You paint cells, place bulbs, or decide where mines are, but all three are the same kind of puzzle: number clues settle, one cell at a time, what each cell must be. And no luck is needed.

Nonogram (the site’s “Nonogram”)

The numbers on each row and column give the lengths of the runs of filled cells. “1 3” means a run of 1, at least one gap, then a run of 3. When everything is filled in, a picture appears.

This puzzle is said to have arisen in Japan around 1987. A graphic editor, Non Ishida, and a professional puzzle author, Tetsuya Nishio, each came up with similar puzzles separately. Which came first can’t be said for sure, and the fun part is that two people had the idea at about the same time. The name “nonogram” is said to have been coined by a British collector, joining Ishida’s “Non” with “diagram.” Publishers and games have given it many other names too.

When a row alone leaves several possibilities, crossing it with the columns shows cells that must be filled or must stay empty. Every picture on this site has exactly one solution and can be finished with row and column information alone.

Bulb Placement (the site’s “Bulb Placement”)

Place bulbs on white cells so that every white cell is lit. Light travels along rows and columns and stops at walls. Two bulbs must never light each other. A number on a wall says how many bulbs sit directly beside it (up, down, left, right).

This puzzle is said to have been devised around 2001 by a reader of a puzzle magazine. It did not come from a professional author but from an ordinary reader’s idea. The hints also teach working backwards: “which positions could light this cell?”

Mine Logic (the site’s “Mine Logic”)

A number tells how many of the 8 surrounding cells hold mines. When a number already has that many flags, its other neighbours are safe. When the remaining mine count equals the number of unknown neighbours, all of them are mines. The puzzles here start with a safe area already open and can be finished without guessing.

Gentle faces, “NP-complete” hearts

Mathematicians have found something these three share: deciding whether a large board has a solution at all is thought to be a problem of the type called “NP-complete.”

• For Nonogram, deciding whether a general board has a solution is said to be NP-complete.
• For Bulb Placement, Brandon McPhail is said to have shown NP-completeness in 2005.
• For mine-style puzzles, Richard Kaye showed it in 2000. But what he showed is not the game itself. It is the question “given a board of numbers, is there a placement of mines that agrees with all of them?” That is a different problem from the real game, which depends on luck.

In plain words, “NP-complete” means that as boards grow, a single fast method that solves every board is probably never going to be found. It does not mean “cannot be solved.” The boards on this site are small, so you can solve them yourself by following the clues. The difficulty grows with size.

Mine Logic on this site offers only boards that need no guessing. That is the other face of Kaye’s question: if you move forward using only what the numbers guarantee, you reach the answer with no luck at all.

How to think about them

• Start with what is certain. In all three, look first for a cell that can only be one thing.
• Combine two sources of information. Rows and columns in Nonogram, lines of sight and wall numbers in Bulb Placement, neighbouring numbers in Mine Logic.
• Turn the question around. Ask “where could a bulb light this cell?” instead of “where should the next bulb go?”

In each of these puzzles the hints start with the idea. See only the idea first, and work out the rest yourself.