The Complexity of TipOver and Other Puzzles

Imagine a warehouse with several vertical stacks of crates. Standing on top of one of the stacks, James Bond has to reach a particular crate. He can't touch the electrified warehouse floor, so he must topple some of the stacks to reach others to eventually get to the target crate. His problem, then, is to figure out the right stacks to tip over in the right directions in the right order. A stack falls as a unit, crates can tip over only into empty spaces, and Bond can't leap across empty space or move diagonally to reach other crates.

This scenario is the basis for an entertaining and challenging puzzle called TipOver, produced by ThinkFun. In 2006, Games magazine named it "puzzle of the year."

TipOver started out as an online game invented by James W. Stephens of Atlanta. It's featured on his PuzzleBeast website as the "Kung Fu Packing Crate Maze." Puzzle inventor M. Oskar van Deventer created the three-dimensional version sold by ThinkFun.

Robert A. Hearn has had a longstanding interest in the connection between combinatorial games and computation. He has proved a variety of results related to computational complexity for sliding-block puzzles, sliding-coin puzzles, plank puzzles, hinged polygon dissections, Amazons, Konane, and others. He has also strengthened existing results or provided new, simpler proofs of complexity for games and puzzles such as Minesweeper, the Warehouseman's Problem, Sokoban, and Rush Hour.

Many of these results were included in Hearn's 2006 doctoral thesis on "Games, Puzzles, and Computation," which became the basis of a book with the same title (CRC Press, 2009) and coauthor Erik D. Demaine (Hearn's thesis adviser).

In the case of TipOver, Hearn proved that this puzzle belongs to a class of computational problems described as NP-complete. He described those results in the article "TipOver is NP-complete," published in the Mathematical Intelligencer (Vol. 28, No. 3, pp. 10-14).

In its starting configuration, a TipOver puzzle has several vertical crates of various heights (1 x 1 x h) arranged on a square grid. A tipper—representing a person navigating the layout—stands on top of a particular starting crate. There is a special 1 x 1 x 1 red crate—the target—elsewhere on the grid.

The tipper can topple any vertical crate that it is standing on, in any of the four compass directions, provided there's enough space for the crate to fall unobstructed and lie flat. The tipper can walk (or climb) along the tops of any crates that are adjacent, even when they have different heights.

In the sample puzzle and solution shown below, the numbers indicate the vertical height of each untoppled crate. The tipper starts on the purple crate. In the first move (top, second from left), the tipper has moved to one of the green crates (3 units tall) and toppled it southward so that it ends up adjacent to a yellow crate that is 2 units tall.

"Surprisingly, it does not take many crates to make an interesting puzzle," Hearn wrote. "The number of tips required can never be more than the number of crates—once a crate has been tipped over, it stays fallen—yet finding the correct sequence can be quite a challenge."

To prove that TipOver is NP-complete, Hearn showed that TipOver puzzles are related to a well-known problem in computer science called the Boolean formula satisfiability (SAT) problem.

Consider, for example, two variables, x and y, and the logical statement (x OR y) AND ((NOT x) OR (NOT y)). The OR means that the clause (x OR y) is true if either x or y is true, and the AND means that the clause (x AND y) is true only if both x and y are true. Solving the given problem means assigning a value of true or false to each of the two variables so that the entire statement is satisfied. Here, x must be true and y false, or vice versa, for the statement to be true.

"For any given instance of SAT, there is a corresponding TipOver puzzle that can be solved just when the SAT problem can be solved," Hearn said.

SAT is the prototypical NP-complete problem. Roughly speaking, an NP problem is one for which it is relatively easy to check whether a given answer is correct, but may require an impossibly long time to solve by any direct procedure. In general, as the number of elements, n, increases, a computer's solution time grows exponentially in the worst case. In effect, systematically solving such a worst-case problem involving many elements can take an enormous amount of time, even on the fastest available computers.

Hearn's results show that TipOver must be at least as hard as SAT. "It's easy to show that TipOver is also no harder than SAT," Hearn said, "so TipOver must be NP-complete as well."

Interestingly, Minesweeper, Tetris, and n x n sudoku also belong to the NP-complete category.

How hard is TipOver? "Is there, perhaps, a clever algorithm for coming up with a solution to a given puzzle instance?" Hearn asked. Probably not, he ed

Hearn has also applied his analytic techniques to plank puzzles, invented by Andrea Gilbert and available as River Crossing from ThinkFun.

In this case, you have to cross a crocodile-infested swamp using only wooden planks supported by tree stumps. You can pick up planks and put them down between other stumps, as long as the stumps are exactly the right distance apart. You can't let planks cross each other or intervening stumps, and you can carry only one plank at a time.

Here's a sample puzzle.

To solve the puzzle, you start by walking across the first plank (length 1) to get to a stump. You pick the plank up, lay it down to the south, walk across it, pick it up again, lay it down to the east, walk across it again, pick it up again, walk across the length-2 plank, lay the length-1 plank down to the east, and so on.

It turns out that plank puzzles belong to the class of computational problems known as PSPACE-complete. Such problems are thought to be computationally harder than their NP-complete counterparts.

"We should not be surprised that [plank puzzles] can be very challenging," Hearn said. "It can be very difficult to determine whether there is a solution, and there are puzzles that take exponentially many moves to escape."

At the same time, no one has yet proved that there is no efficient algorithm for solving all NP-complete (or PSPACE-complete) problems. Indeed, finding an efficient method to solve TipOver could yield the most important computer science result of all time—an achievement worth a $1 million prize.

Originally posted Feb. 19, 2007