Puzzles and tricks from Martin Gardner inspire math and science
Our next example of recreational computer science is inspired by a collection of classic “penny puzzles,” which Gardner wrote about in Scientific American in 1966. Helena Verrill, a mathematician now at Louisiana State University, introduced my father and me to puzzles of this type. You are given a pyramid of six coins, shown on the left in part a of the fourth figure (at right), and your goal is to make a sequence of moves to arrange the coins into a line. But each move you make must place an existing coin into a position that touches at least two other coins. This “two-adjacency” constraint is what makes the puzzle challenging. It might initially seem impossible to get rid of all the three-coin triangles, but with a little insight, it is possible.
There are several coin-sliding puzzles of this type, with the two-adjacency constraint on moves. So again we wondered: How does it generalize? The natural computational question here is whether computers can solve this type of puzzle: Given a starting configuration and a goal configuration of coins, can a computer algorithm determine whether the puzzle is solvable under the two-adjacency constraint, and if so, find a sequence of moves to solve it? Even better, can it find the shortest sequence of moves to solve the puzzle?
Both of these questions are actually still unanswered. I suspect that the second question has a negative answer, and it is computationally intractable to determine the fewest moves needed to solve a puzzle, but no one has proved that yet. However, the first question might have a positive answer, which would be much more interesting—it would essentially provide a general theory for this type of puzzle.
In 1998 Verrill visited my father and me for a couple of days of problem solving, during which we came up with and tackled the first problem. We observed that the puzzle in the fourth figure adheres to a triangular grid: If you draw an equilateral triangular grid where the triangle side length equals the diameter of the coin, then the centers of the coins always remain at grid intersections. This property is a neat consequence of the two-adjacency rule because the coins start on this grid.
For puzzles on the triangular grid, we were able to develop a general computational theory. We found some very simple conditions for when it is possible to transform a starting configuration into a goal configuration via two-adjacency moves. First, the number of coins must be the same in the two configurations, and it must be possible to make at least one two-adjacency move from the starting configuration. Second, and more interesting, the goal configuration must have at least one of three patterns that make it possible to have a last move that solves the puzzle. The patterns are a triangle of three coins, a connected group of four or more coins, and a connected group of three coins along with another connected group of two coins.
As long as the goal configuration has at least one of these patterns, the puzzle is guaranteed to be solvable, and a computer algorithm can tell you how. This result holds even if the coins have different labels (for example, some are heads and some are tails), provided there are more than three coins total.
This kind of simple characterization of solvable puzzles not only helps to find outcomes, but also makes it easy to design new puzzles. Armed with a guarantee about when a puzzle will be solvable, we can design a new one within those constraints that will also be visually interesting. For example, can you solve the puzzle in part b of the fourth figure?
Another special type of coin-sliding puzzle arises if we replace the triangular grid with a square grid, requiring every move to place a coin on this grid. These puzzles are substantially harder to solve, both in practice and in theory. We came up with a nearly complete characterization of solvable puzzles, showing how to complete challenges with at least two “extra coins” to help navigate the other pieces. Puzzles without any extra coins are impossible to solve, and puzzles with just one extra are typically either unsolvable or not too engaging—but we still don’t have a computer algorithm to tell us exactly which puzzles can be solved. The situation with two extra coins is quite interesting, however, and has again allowed us to design several puzzles. Try, for instance, the puzzle in part c of the fourth figure. To see more coin-sliding puzzles, visit http://erikdemaine.org/slidingcoins/.
» Post Comment