17
How the program works
How the program works
…so we shift to
…so we shift to
column 2. But
column 2. But
18
How the program works
How the program works
…and we shift to
…and we shift to
the third column.
the third column.
19
Yet another conflict arises, so we move to the fourth column. The key
idea is that each time we try a particular location for the new queen, we
How the program works
How the program works
…and we shift to
…and we shift to
column 4.
column 4.
There’s still a
There’s still a
20
How the program works
How the program works
…but there’s
…but there’s
nowhere else to
nowhere else to
21
How the program works
How the program works
When we run out of
When we run out of
room in a row:
room in a row:
❐
❐pop the stack,
pop the stack,
22
How the program works
How the program works
Now we
Now we
continue
continue
working on row
working on row
23
How the program works
How the program works
This position has
This position has
no conflicts, so
no conflicts, so
24
How the program works
How the program works
In row 3, we
In row 3, we
start again at the
start again at the
first column.
first column.
ROW 3, COL 1
25
Pseudocode for N-Queens
Pseudocode for N-Queens
❶
❶Initialize a stack where we can keep track of our
Initialize a stack where we can keep track of our
decisions.
decisions.
❷
❷Place the first queen, pushing its position onto the
Place the first queen, pushing its position onto the
stack and setting
stack and setting filled
filled to 0
to 0.
.
❸
❸repeat these steps
repeat these steps
26
Pseudocode for N-Queens
Pseudocode for N-Queens
❸
❸repeat these steps
repeat these steps
❐
❐if there are no conflicts with the queens…
if there are no conflicts with the queens…
Increase filled by 1. If filled is now N, then
27
Pseudocode for N-Queens
Pseudocode for N-Queens
❸
❸repeat these steps
repeat these steps
❐
❐if there are no conflicts with the queens…
if there are no conflicts with the queens…
❐
❐else if there is a conflict and there is room to
else if there is a conflict and there is room to
shift the current queen rightward…
shift the current queen rightward…
Move the current queen rightward,
adjusting the record on top of the stack
to indicate the new position.
28
The last possiblity is that a conflict exists, but the new queen has run
out of room. In this case we backtrack:
Pseudocode for N-Queens
Pseudocode for N-Queens
❸
❸repeat these steps
repeat these steps
❐
❐if there are no conflicts with the queens…
if there are no conflicts with the queens…
❐
❐else if there is a conflict and there is room to
else if there is a conflict and there is room to
shift the current queen rightward…
shift the current queen rightward…
❐
❐else if there is a conflict and there is no room
else if there is a conflict and there is no room
to shift the current queen rightward…
to shift the current queen rightward…
Backtrack!
Keep popping the stack, and reducing filled
by 1, until you reach a row where the queen
can be shifted rightward. Shift this queen right.
29
The potential pitfall: Maybe the stack becomes empty during this
popping. What would that indicate?
Pseudocode for N-Queens
Pseudocode for N-Queens
❸
❸repeat these steps
repeat these steps
❐
❐if there are no conflicts with the queens…
if there are no conflicts with the queens…
❐
❐else if there is a conflict and there is room to
else if there is a conflict and there is room to
shift the current queen rightward…
shift the current queen rightward…
❐
❐else if there is a conflict and there is no room
else if there is a conflict and there is no room
to shift the current queen rightward…
to shift the current queen rightward…
Backtrack!
Keep popping the stack, and reducing filled
by 1, until you reach a row where the queen
can be shifted rightward. Shift this queen right.
30
Watching the program work
Watching the program work
You can double
You can double
click the left mouse
click the left mouse
button here to run
button here to run
the demonstration
the demonstration
program a second
program a second
time:
time:
31
❐
❐Stacks have many applications.
Stacks have many applications.
❐
❐The application which we have shown is called
The application which we have shown is called
backtracking
backtracking.
.
❐
❐The key to backtracking: Each choice is recorded
The key to backtracking: Each choice is recorded
in a stack.
in a stack.
Summary
Summary
32
Presentation copyright 1997, Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright