The history of Lanterns

Lanterns is a young puzzle with an old question behind it: how few lights does it take to see into every corner of a room?

Guarding the gallery

In 1973 the mathematician Victor Klee asked Václav Chvátal a question about museums. If an art gallery is a polygon-shaped room, how many guards, each standing still and looking in every direction, are needed to watch every part of it? Chvátal's answer, published in 1975, is one guard for every three corners of the room, rounded down — and some rooms really do need that many. Steve Fisk later found a famously short proof, by colouring the corners of the room in three colours.

The art gallery problem, as it became known, grew into a whole field of geometry: guards that move, rooms with pillars, galleries in three dimensions. Our puzzle is a tidy grid version of the same idea. A lantern is a guard who can only look along rows and columns, and the walls are the gallery's pillars.

From a puzzle magazine

The puzzle itself appeared in 2001, in the Japanese puzzle magazine of Nikoli, the Tokyo publisher that also gave Sudoku its name. Its first title meant "art museum" — perhaps a nod to the gallery problem. Like Nikoli's other puzzles, it has rules that fit in a few lines, and puzzles made by hand to have exactly one solution, found by reasoning alone.

From there it spread to puzzle books, newspapers and phones around the world, under several names. Ours is called Lanterns, and keeps to the look of the rest of the site: walls in ink, light as a pale wash of pen.

Harder than it looks

The rules are simple, but the puzzle is not. In 2005 Brandon McPhail showed that deciding whether a lantern grid can be solved at all is NP-complete: as boards grow, no known method keeps up with them, because a grid of walls and numbers can be built to work like a logic circuit. That is part of its appeal — a well-made grid still always gives way, one certain step at a time.