[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]

**Held**: Friday, April 10, 1998

- Assignment 6 is now ready. It should be somewhat shorter than past assignments.
- If you celebrate a religious occasion this weekend (Passover, Easter, Id Ulhajj, etc.), I hope you have a good celebration. If not, enjoy your weekend.

- Bailey uses stacks and queues to aid in solving puzzles (a coins puzzle and a maze).
- Let's take a step back and consider a more general problem-solving strategy.
- First of all, how might we represent a generic puzzle? What methods do we need?
- I'd suggest that a
`Puzzle`

object (or interface) would support:- Creation of a new instance of the puzzle (perhaps with some information as to the state of the puzzle).
- Reseting the puzzle to the initial state.
- Creating a list of legal moves at any point.
- Making one of those moves.
- Possibly undoing the last move.
- Copying the current puzzle (so that, for example, we might work on two variant solutions in parallel).
- Comparing 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, simply a way for particular types of puzzles to get information about the move. - Given this class,
*what's a reasonable way to automatically solve the puzzle?* - 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).
- It may be best to ground our discussion in particular problems.

- As Bailey suggests, an interesting problem is that of shuffling
coins.
- 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.

- Can we use this to think about automatic puzzle solving?
- It's clear that it's easy to represent the
*state*of the puzzle (we could simply list the position of each coin). - We clearly wouldn't want to move the dime right and then left again, since that repeats a state we've been in before.
- So, we might check whether we've been in a state before and, if so, skip the move that leads to that state.
- Unfortunatley, a naive implementation of this strategy can also fail to find a correct solution, as it is possible to reach dead ends.
- 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 thepairs 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 moves_to_make; // 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 moves_to_make = current.legalMoves(); for each move in moves_to_make { // This is not legal Java // Make the move next = current; 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.
- 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 solutuions. 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.

- Clearly, we could use our generic puzzle-solving strategy to solve mazes.
- This queue-based solution is typically called a
*breadth-first*exploration of the maze. You look at all the squares of distance one, then all squares of distance two, then all squares of distance three, and so on and so forth. - Unfortunately, this would not be so efficient if you had to do it by walking around the maze, as all squares of distance three may be widly separated in the maze.
- In practice, we typically do a
*depth-first*exploration of the maze. You go as far as you can, making decisions as you go. If you reach the exit, you're done. If not, you back up to your last choice point with choices left to go, make a different choice, and go on. - By using stacks instead of queues in our generic puzzle solver, we can acheive such a search.

On to Introduction to Trees

Back to Stacks and Queues

Outlines:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Current position in syllabus

[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [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.math.grin.edu/~rebelsky/Courses/CS152/98S/home/rebelsky/public_html/Courses/CS152/98S/Outlines/outline.38.html

Source text last modified Tue Jan 12 11:52:28 1999.

This page generated on Mon Jan 25 09:49:45 1999 by SiteWeaver. Validate this page.

Contact our webmaster at rebelsky@math.grin.edu