Puzzles you move and think about

In these puzzles you slide pieces, or yourself, toward a goal. All four look gentle, but ask “what counts as one move?” or “how far ahead should I look?” and they get deep.

Traffic Jam Puzzle (the site’s “Traffic Jam Puzzle”)

On a crowded board, slide the cars to get the red car out of the exit. Each car moves only along the direction it faces. On this site, sliding one car any distance counts as one move. The minimum for each of the 40 levels was checked by breadth-first search (looking at positions nearest the start first, until all are covered). This site’s program checked these numbers (traffic-jam/engine.test.ts).

This kind of puzzle, a car-sliding puzzle, is said to have been devised by the Japanese puzzle designer Nob Yoshigahara (1936–2004) and became widely known after it was sold abroad in the 1990s. Sources disagree on when he devised it: the 1970s, or the late 1970s. Sliding pieces until a target piece reaches an exit is an old idea, shared with the classic Hakoiri Musume. But there is no evidence strong enough to say that one grew out of the other.

Researchers showed that if you let this kind of sliding-block puzzle grow to any size, deciding whether it can be solved belongs to a very hard family of problems (PSPACE-complete). On small boards like the ones here, though, a computer can simply search everything and find the best answer. It is worth not overstating “hard”.

Ice Slide (the site’s “Ice Slide”)

On ice you cannot stop where you like. You keep sliding until you hit a wall or the edge of the board. Sliding across the goal does not finish the level; you must stop on it. Here, one slide is one move.

This trick is a familiar kind of puzzle in video games. Who first made it, and when, is not known.

The key idea is to count only the places where you can stop. Only those stopping places become the next position, so there are far fewer positions to look at than on an ordinary board. The minimum for each of the 24 levels (three each from 2 to 9 slides) was checked by breadth-first search built on this idea. This site’s program checked these numbers (ice-slide/engine.test.ts).

Box Pusher (the site’s “Box Pusher”)

Walk around a warehouse and push every box onto a goal square. You can push a box but never pull it. That is where the difficulty comes from: push a box into a corner by a wall and it can never move again. Here, every single step counts as one move, including a step that pushes a box. The minimum walking steps for the 12 levels (6 to 16 steps) were checked by breadth-first search. This site’s program checked these numbers (box-pusher/engine.test.ts).

This genre is said to have been born in Japan around 1981–82. In 1997 Joseph Culberson showed that deciding whether such a puzzle can be solved belongs to a very hard family of problems (PSPACE-complete). It looks like a child’s toy, yet in computer science it is among the hardest kinds of problem. Small boards, of course, can still be solved normally.

Toggle Lights (the site’s “Toggle Lights”)

Press a cell and that cell and its up, down, left and right neighbors flip. Turn every light off to win. You can choose 3×3 or 5×5. Similar play is said to have existed in electronic toys of the 1970s and 80s.

There is mathematics hiding here. Pressing the same cell twice cancels out. And the order of presses does not matter. So each cell needs only a yes-or-no decision: press or do not press. This site’s program checked these two properties (twice cancels, order does not matter) in toggle-lights/engine.test.ts.

If you calculate in a world of only 0 and 1 where 1 + 1 = 0, the whole board becomes a system of equations. This is called linear algebra over the field with two elements, and it is presented in a 1998 paper by Anderson and Feil.

A handier method is to clear the board from the top. Once you decide the presses in the top row, the presses for row two onward are forced: “clear the light directly above.” On 5×5 the top row has only 2 to the 5th power, 32, patterns. This site’s program tried all 32 to find the minimum and confirmed that it matches the answer of each puzzle. For 3×3, the best counts agree with a separate breadth-first search for all 512 boards.

And on 5×5 there are boards that cannot be fully cleared. For example, a board with only the top-left corner light on cannot be cleared by any presses. The test checks this too.

“One move” differs from game to game

• Traffic Jam Puzzle: sliding a car any distance is one move.
• Ice Slide: sliding until you stop is one move.
• Box Pusher: every step is one move, and so is a step that pushes.
• Toggle Lights: one press is one move.

Change how moves are counted and the “shortest” answer changes. That is why Hakoiri Musume has two answers, 81 and 116 moves. When you see a number, first ask what it counts as a move.

In each of these works, hints start with the idea. Look at only that first, then try again yourself.