[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]

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**

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

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

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

Wednesday, 23 August 2000

- Created as a blank outline.

Thursday, 24 August 2000

- Slight reorganization to page design.

Friday, 17 November 2000

- Filled in the details, based primarily on outline 45 of CSC152 2000S.

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

[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]

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

This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Outlines/outline.45.html

Source text last modified Fri Nov 17 08:53:36 2000.

This page generated on Fri Nov 17 08:55:28 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu