1
❐
❐Chapter 7 introduces the
Chapter 7 introduces the
stack
stack
data type.
data type.
❐
❐Several example
Several example
applications of stacks are
applications of stacks are
given in that chapter.
given in that chapter.
Using a Stack
Using a Stack
2
The N-Queens Problem
The N-Queens Problem
❐
❐Suppose you have 8
Suppose you have 8
chess queens…
chess queens…
3
The N-Queens Problem
The N-Queens Problem
Can the queens be placed on
Can the queens be placed on
the board so that no two
the board so that no two
queens are attacking each
queens are attacking each
other
other ?
?
4
The N-Queens Problem
The N-Queens Problem
Two queens are not
Two queens are not
allowed in the same
allowed in the same
row...
row...
5
The N-Queens Problem
The N-Queens Problem
Two queens are not
Two queens are not
allowed in the same
allowed in the same
row, or in the same
row, or in the same
column…
column…
6
As a quick survey, how many of you think that a solution will be
possible? In any case, we shall find out, because we will write a
program to try to find a solution.
As an aside, if the program does discover a solution, we can easily
check that the solution is correct. But suppose the program tells us that
there is no solution. In that case, there are actually two possibilies to
keep in mind:
The N-Queens Problem
The N-Queens Problem
Two queens are not
Two queens are not
allowed in the same
allowed in the same
row, or in the same
row, or in the same
column, or along the
column, or along the
same diagonal.
same diagonal.
7
The N-Queens Problem
The N-Queens Problem
The number of queens,
The number of queens,
and the size of the board
and the size of the board
can vary.
can vary.
N Queens
8
The N-Queens Problem
The N-Queens Problem
We will write a program
We will write a program
which tries to find a way
which tries to find a way
to place N queens on an
to place N queens on an
N
N x
x N chess board.
N chess board.
If you can run ega or
vga graphics,
you can double click on
this icon with the left
9
How the program works
How the program works
The program
The program
uses a stack to
uses a stack to
keep track of
keep track of
where each
where each
10
How the program works
How the program works
Each time the
Each time the
program decides
program decides
to place a queen
to place a queen
on the board,
on the board,
11
How the program works
How the program works
We also have an
We also have an
integer variable
integer variable
to keep track of
to keep track of
12
How the program works
How the program works
Each time we try
Each time we try
to place a new
to place a new
queen in the next
queen in the next
row, we start by
row, we start by
13
How the program works
How the program works
…if there is a
…if there is a
conflict with
conflict with
another queen,
another queen,
14
How the program works
How the program works
If another
If another
conflict occurs,
conflict occurs,
the queen is
the queen is
15
How the program works
How the program works
When there are
When there are
no conflicts, we
no conflicts, we
16
How the program works
How the program works
Let’s look at the
Let’s look at the
third row. The
third row. The