Adventure Games, Permutations, and Spreadsheets

 

Paul Vodola (PVodola@CAIS.com). Paul Vodola is a Program Scientist and Assistant Program Manager at Systems Planning and Analysis, Inc. in Alexandria, Virginia. He received a Ph.D. in Mathematics at the University of Virginia in 1976. Since then he has worked in the areas of operations research, systems analysis, and modeling but has maintained an interest in group theory and algebra.

 

Puzzles have long been a source of motivation for the exploration of mathematical concepts, theory, and computation. Multimedia adventure games with creative storylines, movies, sophisticated graphics, and sound, are the modern context for both new and classic puzzles. We will show how some of these puzzles can be modeled with directed graphs and the resulting mathematical work can be carried out with nothing more than a computer spreadsheet.

 

Puzzle description and graph model. The adventure game Shivers, by Sierra, takes place in a haunted museum. You, the player, have recklessly accepted a bet to spend the night alone inside . You must wander through rooms collecting objects, manipulating devices, and solving puzzles in order to avoid harm and gain access to areas that might provide escape.

 

One of the puzzles is sketched in Figure 1. We will call it the pinball puzzle because of its operating characteristics. Each of nine colored tiles contains a depression that holds a ball except that the center tileís depression is empty. Each tile except the white center tile is to be matched with a ball of the corresponding color. The eight balls are labeled with the first letter of their color. Below each tile are two flippers capable of batting the ball one or more positions to the right or left. If a ball is flipped into an empty tile, it stays there. Otherwise the ball bounces back to its original tile. The flippers are labeled to show how far, right or left, they can send a ball. In Figure 1, for example, on the orange tile the right flipper (labeled 1L) would shoot the red ball one position left into the red tile. But since the red tile is already occupied, the ball would return to the orange tile. The left flipper (labeled 3R) would move the red ball three places to the right into the white tile where it would occupy the empty depression. Play could then continue by moving some ball into the empty orange tile. The puzzle is solved when the ball and tile colors match and the white tile is empty again.

 

This is clearly a permutation problem, but it is too complex for us to assimilate patterns and develop an orderly approach. Although Figure 1 indicates the destinations of struck balls, since only the empty tile is an admissible destination it might be more useful to visualize which locations flip balls into a given empty position. For example, the only possible opening moves are orange/left, green/right, and blue/left, where color/flipper refers to the color of the tile and the flipper used. Indeed, any time the white tile is empty, one of those three moves must be chosen. We could draw from those three tiles pointing to the white tile to indicate that such transfers are possible. Continuing that line of thought, and using numbers instead of colors, results in the directed graph shown in Figure 2. The numbers at the nodes represent the colors of the tiles as indicated in Figure 1. Only two of the 18 directed edges are labeled with the tile and flipper action that affects the movement. Node 5 is special because it is empty at the beginning and end of the puzzle.

 

From Figure 2, we see quickly that the only opening moves are from nodes 2, 4, and 6. Suppose we move the ball from tile 4. Then the possible moves are from 1 to 4 and from 7 to 4. If we pick 1 to 4 that leaves no choice but to move the ball from 2 to 1. With 2 now empty, we can fill it from 3  or from 5. Choosing the latter leaves 5 empty once again and we have formed a permutation of some of the balls while leaving the others fixed. The ball in tile 4 ended up in tile 2 (this ball moved twice, but our only concern is how the final configuration differs from the original one). The ball in tile 1 ended up in tile 4 and 2 was moved to 1. In short, the balls in tiles 1, 4, and 2 were permuted and the remaining balls were fixed.

 

As is customary, letís write this cyclic permutation by listing within parenthesis the sequence of tiles visited by the balls that move, with the understanding that the ball in the last numbered tile moves to the tile indicated by the first number in the sequence. The cycle created above is ( 1 4 2 ). Another feasible set of moves is 4 to 5, 7 to 4, 8 to 7, and 5 to 8 which creates the cycle ( 4 8 7 ). The goal (see Figure 1) is to obtain the permutation ( 1 4 6 2 ) ( 3 8 7 9 ). Tile 5 is empty at the beginning and end, hence it is a fixed point of the ultimate rearrangement.

 

When operating with Figure 2, it helps to visualize these actions as "pushing the empty space" through a path: rather than moving a ball into the space, think of moving the space into the tile containing that ball. Each move "pushes" to a new position swapping places with the ball it displaces. Each flipper action thus transposes the node occupied by the space and that of the flipper, to which the space is "moving". The admissible movements of the space are those against the direction of arrows in the directed graph of admissible moves of the ball. So letís make a change. Figure 3 is the complementary graph created by reversing all edges in Figure 2. Now the admissible moves of the space are in the direction of the arrows; the remaining notation and conventions do not change.

 

Permutation group model. With practice, we can write down the permutations associated with simple paths taken by the space as it is pushed. This can be formalized by defining a space-path to be a sequence of admissible moves and denoting the path by naming the sequence of nodes occupied by the space. The first space-path used in the examples earlier would be denoted 5-4-1-2-5. The resulting permutation is the product of transpositions ( 5 4 ) ( 4 1 ) ( 1 2 ) ( 2 5 ) formed by moving through the list and creating a transposition from each adjacent pair. In canonical form, as a product of disjoint cycles, that product of transpositions is the single cycle ( 1 4 2 ). Similarly, the second space-path noted earlier is designated 5-4-7-8-5 and it corresponds to the transpositions ( 5 4 ) ( 4 7 ) ( 7 8 ) ( 8 5 ), or as a product of disjoint cycles, ( 4 8 7 ).

 

The concatenation of two space-paths that begin and end at node 5 is another path with the same property. The mechanism for associating transposition products with space-paths shows that the permutation associated with the concatenation is the product of the associated permutations. The composition of the preceding paths above is 5-4-1-2-5-5-4-7-8-5 = 5-4-1-2-5-4-7-8-5 and the associated product ( 1 4 2 ) ( 4 8 7 ) is ( 1 8 7 4 2 ). Note that in interpreting space-paths, strings of repeated 5ís are replaced by a single occurrence. (This could be interpreted as adding a directed edge from each node to itself. It essentially acts as a "do nothing" operation within a space-path.)

 

The desired solution to the entire puzzle can thus be expressed as a certain space-path, because space-paths are an abstract model of the flipper operations controlling the puzzle. The solution path might be quite long, but it can be decomposed into smaller elementary space-paths. Visualize the solution space-path as a string of digits that starts and ends with 5. Proceed through that path from left to right creating a subpath from each interval of digits between consecutive occurrences of the digit 5. Let adjacent sub-paths share the 5 that separates them, so that they also form space-paths that begin and end at node 5. These elementary subpaths then have the property that the space does not pass a second time through node 5 until termination of the sub-path. The permutations associated with such subpaths therefore all have the property that they fix the letter 5. The collection G of permutations associated with space-paths that start and end at node 5 forms a group. (Note from Figure 3 that any move of the space can be inverted, although it may take several moves to do so.)

 

The desired solution is to express the permutation ( 1 4 6 2 ) ( 3 8 7 9 ), which transforms the initial configuration (Figure 1) into the desired state, with each colored ball resting on its matching tile, as a product of members of G. (We have no guarantee that this is possible, but we trust the designer of the pinball puzzle did not create an impossible task!)

 

While transforming the puzzle into a permutation problem seems promising, it really just replaces a trial-and-error sequence of flipper actions with a trial-and-error permutation multiplication problem. Consider a comparable problem in arithmetic: is the number 25470 expressible as a product from the list of numbers 3, 6, and 35, allowing repeated factors? Someone proficient with spreadsheets, but unaware of number theory, would have no problem implementing the following brute force approach. Form a table of all products of pairs of numbers chosen from the list { 1, 3, 6, 35 } including repeated factors such as 66. This produces all products using two or fewer numbers from { 1, 3, 6, 35 }. Sort these products in order of increasing size, discarding any duplicates, and look for 25470. (Spreadsheets have built-in commands for these operations.) If 25470 does not appear, repeat the process choosing the two factors from this new, larger list. The result, after sorting and culling duplicates, is a list of all products of four or fewer factors. After n iterations the list will consist of all products of 2n or fewer factors. At some step either the desired number 25470 will appear or all new products will exceed 25470. In the latter case the answer is no, because further products would be still larger. For moderate sized numbers, this process would take only a few seconds.

 

Excel algorithms. In the pinball puzzle problem, potential factors are permutations associated with the elementary space-paths that include node 5 only at the endpoints. We have already identified two by inspecting Figure 3 and it is easy to spot a few more. Can a collection of such factors be found from which ( 1 4 6 2 ) ( 3 8 7 9 ) can be expressed as a product? We could use the same brute force approach that we applied to the arithmetic problem if we could manipulate permutations on a spreadsheet as easily as numbers and text. A collection of permutation functions and related utilities that will give us these capabilities, written for the Microsoft Excel spreadsheet, is described below

 

SimplifyCycles is an Excel function that accepts a character string representation of potentially overlapping cycles and returns the product permutation in canonical form as a product of disjoint cycles. The steps are the same as those generally used with pencil and paper. The first column of Table 1 consists of input strings of cycles that were manually typed. The second column shows the results of SimplifyCycles. The MultiplyCycles function takes two string representations of permutations and multiplies them by concatenating the strings and calling SimplifyCycles. The PathToPerm function creates the permutation associated with a space-path. It inputs the letters that define the path, separated by spaces. The transposition expression is created internally and passed through SimplifyCycles for output.

 

The space-paths used in earlier examples have been typed into the second column of Table 2 and concatenated at the bottom using "&" (Excelís concatenation operator). The third column uses PathToPerm to associate the paths with permutations. The last column shows the running product of the permutations, from MultiplyCycles. Since there are only two entries, the first entry repeats the first permutation and the second entry is the product ( 1 4 2 ) ( 4 8 7 ). Note that the permutation associated with the concatenation of space-paths is the product of the permutations associated with each path in the same order as the concatenation.

 

Solution of the Pinball Puzzle. Table 3 is a list of space-paths and associated permutations derived from a rudimentary inspection of Figure 3. Each has been labeled with a letter symbol to make tracking easier when products are formed. At this point, one might experiment with products of these generators, perhaps looking back at Figure 3 to see if anything new can be gleaned from the diagram. The power of spreadsheets is that one can survey an enormous number of approaches and calculations while waiting for inspiration to arrive.

 

In case inspiration is on a later train, here is an Excel macro that implements the brute-force approach outlined earlier for the arithmetic problem. GenPermProd generates the products of all pairs of permutations appearing in a list. If the user assigns a label to each permutation, the macro will concatenate the labels each time it forms a pairwise product so that the labels for the products are maintained along with the permutation products. The user selects a list of permutations and associated labels on any worksheet by highlighting them in adjacent columns using the mouse. The macro separates duplicate expressions and outputs the list of products in a symbol/permutation format suitable for selection and repeated application of the macro.

 

The results of the first invocation of the macro, using the data outlined in Table 3, are shown in Table 4. The four original elements together with their 16 products form a list of 19 distinct permutations; there is one duplicate: AC = CA. The list is small enough to let us see that the desired permutation, ( 1 4 6 2 ) ( 3 8 7 9 ), does not appear. But the two columns are in the right format to be selected for a second pass of the macro.

 

A small portion of the results of the second macro invocation are shown in Table 5. There are actually 257 different Table 5 contains the desired solution as the expression BADD (shown in boldface). Excelís Edit|Find command lets us find it in the list by searching for the solution permutation string.

Taking the solution expressed as a product of the four generators, we can convert the sequence BADD back into a space-path, which in turn is translated into flipper selections.

 

Considering how much effort went into finding the solution, using techniques and tools unfamiliar to the untrained person, surely any player with the insight or persistence required to complete the puzzle deserves bonus points! The puzzle designer has applied to a given configuration a sequence of permutation operations from some group of permutations. The solverís task tries to discover how to express the inverse permutation as a product of a given set of generators of this group.

 

Related Problems and Puzzles. The graph for the pinball puzzle is a more useful tool for understanding the puzzleís properties and behavior than the puzzle itself. A similar but even more striking example of the utility of the model is provided by the knight puzzle found in the game The 11th Hour by Trilobyte. Two knights of each color sit on an irregular fragment of a chessboard as shown in Figure 4. They move as in chess (without the requirement that alternate moves be by alternate colors) and must remain on the fragment. Can they be moved so that the white and black knights exchange positions?

 

The reader may wish to explore the puzzle before reading further.

 

 

Number the squares as shown in the figure and build a graph by connecting two nodes if they are associated with squares that a knight can traverse in a single move. The graph, annotated to show the initial positions of the knights, can be seen in Figure 5.

 

The graph alone may make you cry "voilà". Node 3 provides convenient "off-street parking" for any knight the player wishes to place in the next available upper position; that is, the knights can be shuttled into the lower nodes while dropping off any desired knight at node 3. That knight can then be moved upward and the process repeated. The puzzle is so flexible that more complicated variations can also be solved. If the knights were individually distinguished, say by the letters A through D, you could create any of the 4!=24 possible permutations of their initial positions -- even if squares 4 and 5 were removed from the board fragment!

 

Rearrangement puzzles. The knight and pinball puzzles are examples from a family of rearrangement puzzles that can be designed and modeled using a directed graph or an undirected graph. Design options include the addiing and removing nodes and edges; changing the directions of edges; altering the relative number of filled and empty nodes; and either distinguishing between all objects, as in the pinball puzzle, or consider various subsets to be equivalent, as in the knight puzzle. Each designer must establish initial positions and objectives that are compatible with the constraints of the graph. Provided that each move is invertible, (perhaps in several moves) the set of permitted rearrangements will always form a group. The size of the group of permissible rearrangements generally determines the level of challenge to the player, who seeks to solve the inverse problem posed by the designer.

 

The group of permissible rearrangements of the knights is S4, the symmetric group on four letters. What about the group of possible permutations of the eight balls in the pinball puzzle (assuming, as always, the center white tile remains empty)? The upper bound would be all of S8 but the size of S8 (8! = 40320) makes the brute force computation of all possible products a challenge. Note that if the group were not all of S8, then for some initial configurations the balls could not be moved to matching tiles by any sequence of flipper actions. It takes some knowledge of permutation group theory to find the group G of rearrangements of the pinball puzzle.

A fairly complete understanding exists for the archetypal rearrangement puzzle, often called the 15-puzzle, whose frame contains 15 numbered tiles and a space (Figure 6). The tiles are scrambled and must be restored to the order shown. Adjacent tiles can slide into the space but cannot be removed or otherwise manipulated. Interestingly, the graph is so similar to the mechanical puzzle that it offers little, if any, additional insight. On the other hand, group theory -- which might be regarded as the most abstract model for the puzzle, leads to a complete understanding of the puzzle and the recognition that A15, the alternating group on 15 letters, is the group of rearrangements associated with the puzzle [3]. Stein [4] provides some insight into the 15-puzzle and other rearrangement problems. Wilson [5] discusses the general structure of graphs and their groups including the determination of the groups associated with all undirected graphs. The spreadsheet functionality offered here, together with the theory and application of permutation groups found in references [1] and [2], may be sufficient for you to explore and determine of the groups associated with the pinball puzzle and other puzzles modeled by graphs.

 

Computer adventure games contain a variety of mathematically oriented puzzles involving mazes, modular arithmetic, variations on rearrangements, and linear algebra. Other games, such as The 7th Guest by Trilobyte and Jewels of the Oracle by Discis incorporate puzzles in their design. There are also many Internet sites devoted to games including the discussion and solution of puzzles. The algorithms used in this article can be obtained over the Internet at the Mathematics Archives (http://archives.math.utk.edu). The functions and subroutines are contained in an Excel workbook along with additional algorithms and materials related to permutation groups and puzzles.

References

  1. G. Birkhoff and S. MacLane, A Survey of Modern Algebra, revised edition, The MacMillan Company, New York, 1953.
  2. I. N. Herstein, Topics in Algebra, 2nd edition, John Wiley & Sons, Inc., New York, 1975.
  3. E. Spitznagel, Jr., A New Look at the Fifteen Puzzle, Mathematics Magazine, Vol. 40 (1967) 171-174.
  4. S.K. Stein, Mathematics: The Man-Made Universe, W.H. Freeman and Company, New York, 1976, Third Edition.
  5. R.M. Wilson, Graph Puzzles, Homotopy, and the Alternating Group, Journal of Combinatorial Theory (B) 16 (1974) 86-96.

 

Acknowledgment. I would like to thank my good friend George Mackiw for his encouragement and support in writing this article.