# Class 45: Automated Problem Solving with Linear Structures

Back to Priority Queues, Heaps, and Heap Sort. On to Introduction to Trees.

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

## Puzzles

• 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

• 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 |
+---+---+---+
```

### Mazes

• A maze is a collection of cells with ``walls'' between selected cells, along with a starting cell and an ending cell.
• For example
```+---+---+---+---+
| S         |   |
+   +---+   +---+
|       |   |   |
+---+   +   +---+
|       |       |
+   +   +---+---+
|   |   |       |
+---+   +   +   +
|   |       | F |
+---+---+---+---+
```
• A ``move'' in a maze consists of stepping to an adjacent space with no adjacent wall.
• Not all mazes are necessarily solvable.

### A Coins Puzzle

• 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.

## Modeling Puzzles

• 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.

### Implementing Puzzles

• 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)

## Solving Puzzles

• 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?
```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();
// 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)) {
} # 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.

### Selecting a 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 |
+---+---+---+      +---+---+---+
```

### Using Queus for Solving

• 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.

### Using Stacks for Solving

• 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.

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Friday, 17 November 2000

Back to Priority Queues, Heaps, and Heap Sort. On to Introduction to Trees.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.