Held Friday, November 17, 2000
Summary
Today, we'll visit an application of linear structures: automated puzzle
solving. Along the way, we'll consider some object-oriented design
issues.
Notes
- I'll be gone on Monday (traveling back from my aunt's memorial service).
Mr. Stone will teach class on trees.
- Please read the chapter in Bailey on trees. (Yes, it comes before
the chapter on heaps.)
- Don't forget that homework 4 is due.
- I expect to give you one more homework, probably involving applets.
- Have a good weekend! I'll see you Tuesday.
Overview
- For today's class, we're going to consider how we might use computers
to ``solve'' some simple puzzles.
- In particular, we will use linear structures to help us automate the
solving of puzzles.
- Note that this is one of the three key issues we consider when developing
abstract data types: facilities, implementation, and applications.
- In some ways, this problem is similar to that of our Othello game. In
other ways, it is different (in part because we have only one player).
- What do I mean by puzzles? Perhaps it's best to begin with some
examples.
- The eights puzzle has eight pieces, numbered from 1 to 8 in a 9x9
grid.
- The basic move is to slide a piece into an adjoining space.
- The goal is to
get them ``in order''
- The solution to the eights puzzle is
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | |
+---+---+---+
- Here's one ``starting state''
+---+---+---+
| 4 | | 2 |
+---+---+---+
| 5 | 1 | 8 |
+---+---+---+
| 7 | 6 | 3 |
+---+---+---+
- Here's another
+---+---+---+
| | 3 | 5 |
+---+---+---+
| 2 | 4 | 6 |
+---+---+---+
| 7 | 1 | 8 |
+---+---+---+
- This is the one from Bailey, which I call the coins puzzle.
- Note that when I taught from the draft of Bailey, one of my students
caught an error in the problem :-)
- You begin with coins arranged biggest to smallest (in terms of
radius, not value).
- Your goal is to reverse the order of the coins.
- You are only allowed to move smaller coins onto bigger coins
or onto blank squares).
- There is one blank square to the right of all the coins.
- Bailey cleverly observes that if we use a queue as our linear structure,
then the first solution printed out is also one of the optimal solutions.
Why? Because of the structure of queues. First, all the states
reachable in 0 moves are added, as each is removed and its successors
are added, only those reachable in 1 move are added, as each is
removed and its successors are added, only those reachable in 2 moves
are added. So, we consider the reachability in order.
- Soon, we'll consider general techniques for solving puzzles.
- First we might consider we how to represent a generic puzzle.
In particular, what methods do we need?
- I'd suggest that a
Puzzle object (or interface) would
support:
- Create a new instance of the puzzle (perhaps with some information
as to the state of the puzzle).
- Reset the puzzle to the initial state.
- Build a list of legal moves at any point.
- Make one of those moves.
- Undo the last move (possibly).
- Copy the current puzzle (so that, for example, we might work on
two variant solutions in parallel).
- Compare two states of a puzzle (or two puzzles).
- ...
- As this suggests, we'll also need a
Move class (or
interface).
- It's likely that we won't need much in the class.
- Rather, these serve as shorthands for representing ``what can be
done next''.
- It might also be useful to separate the ``Board'' used for the
puzzle from the ``Rules'' for the puzzle.
- The particular models are relatively easy.
- Eights puzzle:
- The board could be a 3x3 array of integers. 0 would represent ``empty''.
- A move is a pair of ``indices'' (row,column) representing the cell to
move from and the cell to move to.
- A move is legal if the from cell is not empty, the destination cell is
empty, and either the row or the column (but not both) differ by 1.
- Maze puzzle:
- How might we represent the board?
- Note that we should keep track of the ``current cell''
- Do we want to allow ``one-way'' walls? (Does it make a difference?)
- Do we want to allow ``diagonal'' moves?
- A move is simply a direction (N, S, E, W).
- Coins puzzle:
- For the board, we could keep track of what is in each cell or where
each coin is.
- A move is simply a coin and a direction (left or right)
- Since we've described puzzles uniformly, it may also be possible
to solve them uniformly.
- Let's take a step back and consider a few general problem-solving
strategy.
- Given these classes, what area reasonable ways to automatically
solve puzzles?
- Most people start with something on the order of
while (!solved) {
pick a legal move
make that move
}
- Unfortunately, in many puzzles, this doesn't guarantee termination
(that is, you could alternate between two different states of the puzzle).
- In our eight's puzzle, we might keep moving a piece back-and-forth.
- However, you also can't refuse to go back to a previous state. In our
maze, if we'd gone East right first, we'd need to ``back up'' and go
south.
- What this means is that we'll probably need to keep track of
all the boards and moves that can be made, possibly returning to an
old state when necessary.
// As long as we haven't found a solution AND
// there is a board state + legal move combination we haven't tried
// Pick one of those combinations
// Make the move
- We can use any linear structure to keep track of the pairs
of board state and legal move. It's easy to store them by actually
making the move (and, perhaps, keeping track of the move we just made).
- In something closer to Java (but not precisely java)
/**
* Find a solution to a puzzle using a brute-force method.
* Pre: The puzzle has been initialized.
* Post: The solution is printed.
*/
public void solve(Puzzle p) {
Set checked = new Set(); // The boards we've already checked
MoveList movesToMake; // The moves from current pos.
Linear todo = new Linear(); // The boards we still need to check
Puzzle current; // The current state of the puzzle
Puzzle next; // The next state of the puzzle
// Start at the beginning
current = p;
current.reset();
checked.add(current);
todo.add(current);
// Keep going until we find a solution (exit within loop) or
// run out of things to try.
while (!todo.empty()) {
// Get the next state of the puzzle to try.
current = todo.remove();
// Is it a solution?
if (current.solved()) {
print "Solved the puzzle. Guess how."
return;
}
// If not, consider all alternatives
movesToMake = current.legalMoves();
for each move in movesToMake { // This is not legal Java
// Make the move
next = current.clone();
next.makeMove(move);
// If we haven't seen the position, add it as something to consider
if (!checked.contains(next)) {
checked.add(next);
todo.add(next);
} # if we haven't seen this position yet
} // for each
} // while
print "The puzzle had no solution.";
} // solve
- We might also extend our code to print the solution. In particular,
we can use pairs consisting of the board and the moves to get there in
the linear structure.
- What linear structure should we use to store the ``partial solution
states''?
- We'll note that we can represent the ``options'' pictorially, as
a form of tree.
This may help in our consideration (and remind us why we check to see
if we've seen things already).
Starting-State
/ | \
move move move
/ | \
State01 State02 State03
/ |
move move ........
/ |
State04 State05
- In our eights puzzle game, we might draw
+---+---+---+
| 4 | | 2 |
+---+---+---+
| 5 | 1 | 8 |
+---+---+---+
| 7 | 6 | 3 |
+---+---+---+
|
+------------------+------------------+
| | |
move the 4 move the 1 move the 2
+---+---+---+ +---+---+---+ +---+---+---+
| | 4 | 2 | | 4 | 1 | 2 | | 4 | 2 | |
+---+---+---+ +---+---+---+ +---+---+---+
| 5 | 1 | 8 | | 5 | | 8 | | 5 | 1 | 8 |
+---+---+---+ +---+---+---+ +---+---+---+
| 7 | 6 | 3 | | 7 | 6 | 3 | | 7 | 6 | 3 |
+---+---+---+ +---+---+---+ +---+---+---+
| ... ...
|
+------------------+
| |
move the 4 move the 2
+---+---+---+ +---+---+---+
| 4 | | 2 | | 4 | 2 | |
+---+---+---+ +---+---+---+
| 5 | 1 | 8 | | 5 | 1 | 8 |
+---+---+---+ +---+---+---+
| 7 | 6 | 3 | | 7 | 6 | 3 |
+---+---+---+ +---+---+---+
- Suppose we used a queue. What can we say about the solution
strategy or the solution we get?
- Let's consider how many moves are made for each partial solution.
- Note that the first state in the queue requires 0 moves.
- Anything put in the queue from that state requires 1 move.
- We remove the first thing from the queue that requires 1 move;
anything we put in next requires 2 moves. The 2 move states
follow the 1 move states.
- And so on down the line.
- Hence, the solution (if we find one), requires the fewest
moves.
- Note that we are, in effect, moving across each level of the solution
space. This is called a breadth-first exploration.
- Suppose we used a stack instead? Is there a reason to do so?
- In thinking about real-world problem solving, you typically can't make
``copies'' of puzzles. Rather, you make a move and then have to
back up if you want to try an alternate.
- If we used a queue, we'd be spending a lot of time backing up.
- In such a world, you typically prefer to go as far as you can from
a particular decision, only backing up when you realized that the
decision was incorrect.
- This is called a depth-first exploration of the solution space.
- By using a stack, we can get such exploration. Suppose we have two
choices at the beginning (as in our maze). We push both choices, and
then select one. We push the choices from that position on
top. Hence, we keep exploring forward until one route exhausts itself.
Only then do we back up.
- In practice, we might need to keep track of how to back up.