Lecture Data structures and other objects using C++ - Chapter 7: Using a stack - Trường Đại học Công nghiệp Thực phẩm Tp. Hồ Chí Minh
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (688.74 KB, 10 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=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.
This presentation shows
This presentation shows
another use called
another use called
backtracking to solve the
backtracking to solve the
NQueens problem
NQueens problem..
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
Suppose you have 8
Suppose you have 8
chess queens...
chess queens...
...and a chess board
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
<i>Can the queens be </i>
<i>placed on the board so </i>
<i>that no two queens are </i>
<i>attacking each other </i>
<i>?</i>
</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>
Two queens are not
Two queens are not
allowed in the same
allowed in the same
row...
</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>
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...
</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>
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.
</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>
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 ro
ws
</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>
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
</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>
The program
The program
uses a stack to
uses a stack to
keep track of
keep track of
where each
where each
queen is placed.
</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10></div>
<!--links-->
