Ivars Peterson's MathTrek

October 24, 2005

Sliding Around

Here's a seemingly simple puzzle.


Credit: Courtesy of Robert A. Hearn

Place four coins on the bottom row of circles (G, D, E, and R), leaving the letters MARTIN exposed. Your challenge is to slide the coins along the paths joining the circles so that the four coins cover the top row of circles (M, T, I, and blank), exposing the letters GARDNER.

Sounds simple? The catch is that at no time are two coins allowed to be next to each other when a path joins the two circles. For example, you can't move the G coin initially because the only allowed move would put it next to the D coin. The D coin can move to the T circle but not to the A circle or the I circle. You also have to slide the coins one at a time, all the way from one circle to another. And, where paths cross, you can't switch from one path to another en route.

Robert A Hearn, a graduate student at the MIT Artificial Intelligence Laboratory, invented this puzzle in honor of Martin Gardner, mathemagician extraordinaire.

In traditional sliding-coin puzzles, a set of coins laid out in a certain arrangement must be slid into a new configuration in the fewest possible moves (see "Sliding-Coin Puzzles" at http://www.sciencenews.org/articles/20030201/mathtrek.asp). It's been proved for these types of puzzles that it's always computationally "easy" to determine whether a given puzzle is solvable.

Hearn's Martin Gardner coin-sliding puzzle, however, is a different sort of beast. It's more akin to sliding-block puzzles, such as the infamous 14-15 puzzle (see "Logic in the Blocks" at http://www.sciencenews.org/articles/20020817/bob10.asp), than to traditional sliding-coin puzzles.

It happens to take 25 moves to solve the Martin Gardner puzzle. In exploring how hard it might be solve such puzzles in general, Hearn discovered that there's a relatively simple way to generate arbitrarily difficult instances. Indeed, it's easy to make puzzles for which it's computationally very difficult to determine whether there's a solution at all.

More formally, it turns out the Hearn's new type of puzzle belongs to a category of computational problems described as PSPACE-complete. This means that you should expect that, as the number of circles and paths gets larger, the amount of computer time required to solve the puzzle increases exponentially, even though the amount of memory required increases merely algebraically with size.

Here's another puzzle for you to try.


Place four coins on the red circles. Slide the coins along the paths so that there is a coin on every starred circle. At no time may any two coins be adjacent—occupying two circles joined by a path. You should be able to solve this puzzle in 28 moves.
Credit: Bob Hearn

Hearn has tried a number of variations, such as using tokens or coins of different colors. "Then the start and end configurations have specific places for each color of token," Hearn says. "This makes more complex puzzles possible on smaller graphs." Mathematically, a graph is an array of vertices or nodes (circles in this case) connected by edges (paths).


Credit: Bob Hearn
In this puzzle, each of four tokens has a different color, initially placed as shown by the colored dots. Your goal is to move each token to a space containing a circle of the same color. Solving this particular puzzle requires 116 moves.

Hearn's Martin Gardner coin-sliding puzzle also inspired puzzle designer James Stephens, who runs the PuzzleBeast Web site (http://www.puzzlebeast.com/), to create a computer-generated set of puzzles called the "Meandering Monk Maze." You can try them online at http://www.puzzlebeast.com/monkmaze/index.html.

Additional puzzles by Bob Hearn. [link to pdf file]

Copyright © 2005 by Ivars Peterson

References:

Demaine, E.D., and M.L. Demaine. 2005. Sliding-coin puzzles. In Tribute to a Mathemagician, B. Cipra, E.D. Demaine, M.L. Demaine, and T. Rodgers, eds. Wellesley, Mass.: A K Peters.

Gardner, M. 2005. Martin Gardner's Mathematical Games: The Entire Collection of His Scientific American Columns. Washington, D.C.: Mathematical Association of America.

Hearn, R.A. 2005. The complexity of sliding-block puzzles and plank puzzles. In Tribute to a Mathemagician, B. Cipra, E.D. Demaine, M.L. Demaine, and T. Rodgers, eds. Wellesley, Mass.: A K Peters.

Peterson, I. 2003. It's not you, it's the puzzle. Muse 7(March):21. Available at http://www.sciencenewsforkids.org/pages/puzzlezone/muse/muse0303.asp.

______. 2003. Sliding-coin puzzles. MAA Online (Feb. 3).

______. 2002. Logic in the blocks. Science News 162(Aug. 17):106-108. Available at http://www.sciencenews.org/articles/20020817/bob10.asp.

To learn more about the computational complexity of games and puzzles, go to http://www.ics.uci.edu/~eppstein/cgt/hard.html.

Information about and examples of sliding-block puzzles are available at http://www.puzzleworld.org/SlidingBlockPuzzles/default.htm.

The "Meandering Monk Maze" puzzle at http://www.puzzlebeast.com/monkmaze/index.html was inspired by Hearn's Martin Gardner coin puzzle.

Bob Hearn has a Web page at http://www.swiss.ai.mit.edu/~bob/.