tailieunhanh - Lecture Data structures and other objects using C++ - Chapter 7: Using a stack

This lecture demonstrates an application of stacks: implementing backtracking to solve the N-Queens problem. The presentation includes a demonstration program which you can run at a couple points during the presentation. The demonstation requires EGA or VGA graphics on a PC. The best time for this lecture is after the students have read chapter 7 on stacks. | Chapter 7 introduces the stack data type. Several example applications of stacks are given in that chapter. This presentation shows another use called backtracking to solve the N-Queens problem. Using a Stack Data Structures and Other Objects Using C++ This lecture demonstrates an application of stacks: implementing backtracking to solve the N-Queens problem. The presentation includes a demonstration program which you can run at a couple points during the presentation. The demonstation requires EGA or VGA graphics on a PC. The best time for this lecture is after the students have read Chapter 7 on stacks. If the students want additional information about the N-queens problem, you can direct them to Programming Project 9 in Chapter 7. The N-Queens Problem Suppose you have 8 chess queens. .and a chess board We'll start with a description of a problem which involves a bunch of queens from a chess game, and a chess board. The N-Queens Problem Can the queens be placed on the board so that no two queens are attacking each other ? Some of you may have seen this problem before. The goal is to place all the queens on the board so that none of the queens are attacking each other. The N-Queens Problem Two queens are not allowed in the same row. If you play chess, then you know that this forbids two queens from being in the same row. The N-Queens Problem Two queens are not allowed in the same row, or in the same column. .or in the same column. The N-Queens Problem Two queens are not allowed in the same row, or in the same column, or along the same diagonal. .or along the same diagonal. 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 | Chapter 7 introduces the stack data type. Several example applications of stacks are given in that chapter. This presentation shows another use called backtracking to solve the N-Queens problem. Using a Stack Data Structures and Other Objects Using C++ This lecture demonstrates an application of stacks: implementing backtracking to solve the N-Queens problem. The presentation includes a demonstration program which you can run at a couple points during the presentation. The demonstation requires EGA or VGA graphics on a PC. The best time for this lecture is after the students have read Chapter 7 on stacks. If the students want additional information about the N-queens problem, you can direct them to Programming Project 9 in Chapter 7. The N-Queens Problem Suppose you have 8 chess queens. .and a chess board We'll start with a description of a problem which involves a bunch of queens from a chess game, and a chess board. The N-Queens Problem Can the queens be placed on the board so .