A Dicey Problem |
The three-by-three array in Figure 1 is a maze. A standard six-sided die is needed to traverse the maze (the layout of a standard six--sided die is shown in Figure 2). Each maze has an initial position and an initial die configuration. In Figure 1, the starting position is row 1, column 2--the ``2'' in the top row of the maze--and the initial die configuration has the ``5'' on top of the die and the ``1'' facing the player (assume the player is viewing the maze from the bottom edge of the figure).
To move through the maze you must tip the die over on an edge to land on an
adjacent square, effecting horizontal or
vertical movement from one square to another. However, you can only move onto a
square that contains the same
number as the number displayed on the top of the die before the move, or
onto a ``wild'' square which contains a star.
Movement onto a wild square is always allowed regardless of the number
currently displayed on the top of the die. The
goal of the maze is to move the die off the starting square and to then
find a way back to that same square.
For example, at the beginning of the maze there are two possible moves.
Since the 5 is on top of the die, it is possible to
move down one square, and since the square to the left of the starting position
is wild it is also possible to move left. If
the first move chosen is to move down, this brings the 6 to the top of the
die and moves are now possible both to the right
and down. If the first move chosen is instead to the left, this brings the 3
to the top of the die and no further moves are
possible.
If we consider maze locations as ordered pairs of row and column
numbers (
row, column)
with row indexes starting at 1
for the top row and increasing toward the bottom, and column indexes
starting at 1 for the left column and increasing to
the right, the solution to this simple example maze can be
specified as: (1,2), (2,2), (2,3), (3,3), (3,2), (3,1), (2,1), (1,1),
(1,2). A bit more challenging example maze is shown in Figure 3.
The goal of this problem is to write a program to solve dice mazes. The input
file will contain several mazes for which
the program should search for solutions. Each maze will have either a unique
solution or no solution at all. That is, each
maze in the input may or may not have a solution. For each input maze, either a solution or a message indicating no
solution is possible will be sent to the output.
DICEMAZE1 3 3 1 2 5 1 -1 2 4 5 5 6 6 -1 -1 DICEMAZE2 4 7 2 6 3 6 6 4 6 0 2 6 4 1 2 -1 5 3 6 1 5 3 4 5 6 4 2 4 1 2 0 3 -1 6 DICEMAZE3 3 3 1 1 2 4 2 2 3 4 5 6 -1 -1 -1 END
DICEMAZE1 (1,2),(2,2),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2) DICEMAZE2 (2,6),(2,5),(2,4),(2,3),(2,2),(3,2),(4,2),(4,1),(3,1), (2,1),(2,2),(2,3),(2,4),(2,5),(1,5),(1,6),(1,7),(2,7), (3,7),(4,7),(4,6),(3,6),(2,6) DICEMAZE3 No Solution Possible