数据结构与程序设计(12)-八皇后问题

《数据结构与程序设计(12)-八皇后问题》由会员分享，可在线阅读，更多相关《数据结构与程序设计(12)-八皇后问题（32页珍藏版）》请在装配图网上搜索。

1、数据结构与程序设计(12)王丽苹9/1/20231数据结构与程序设计 Eight-Queens PuzzlenBook P183-1849/1/20232数据结构与程序设计 Four-Queens solution9/1/20233数据结构与程序设计 Four-Queens solution9/1/20234数据结构与程序设计 Program Outline9/1/20235数据结构与程序设计 Eight-Queens Puzzlen目录EightQueens下例程9/1/20236数据结构与程序设计 Eight-Queens Puzzlenconst int max_board=30;ncl

2、ass Queens npublic:n Queens(int size);n bool is_solved()const;n void print()const;n bool unguarded(int col)const;n void insert(int col);n void remove(int col);n int board_size;/dimension of board=maximum number of queensnprivate:n int count;/current number of queens=first unoccupied rown bool queen_

3、squaremax_boardmax_board;n;9/1/20237数据结构与程序设计 Eight-Queens Puzzlenbool Queens:is_solved()constnn return(count=board_size);n9/1/20238数据结构与程序设计 Eight-Queens Puzzlenvoid Queens:print()constnnint i,j;nfor(i=0;iboard_size;i+)nnfor(j=0;jboard_size;j+)nn cout queen_squareij flush;nncout endl;nncoutendlendl

4、;n9/1/20239数据结构与程序设计 Eight-Queens Puzzlenvoid Queens:remove(int col)nn queen_square-countcol=false;n9/1/202310数据结构与程序设计 Eight-Queens Puzzlenvoid Queens:insert(int col)n/*nPre:The square in the first unoccupied row(row count)and column coln is not guarded by any queen.nPost:A queen has been inserted

5、into the square at row count and columnn col;count has been incremented by 1.n*/nn queen_squarecount+col=true;n9/1/202311数据结构与程序设计 Eight-Queens PuzzlenQueens:Queens(int size)n/*nPost:The Queens object is set up as an emptyn configuration on a chessboard with size squares in each row and column.n*/nn

6、 board_size=size;n count=0;n for(int row=0;row board_size;row+)n for(int col=0;col board_size;col+)n queen_squarerowcol=false;n9/1/202312数据结构与程序设计 Eight-Queens Puzzle p191nbool Queens:unguarded(int col)constn/*nPost:Returns true or false according as the square in the firstn unoccupied row(row count

7、)and column col is not guarded by any queen.n*/nn int i;n bool ok=true;/turns false if we find a queen in column or diagonaln for(i=0;ok&i=0&col-i=0;i+)n ok=!queen_squarecount-icol-i;/Check upper-left diagonaln for(i=1;ok&count-i=0&col+i board_size;i+)n ok=!queen_squarecount-icol+i;/Check upper-righ

8、t diagonaln return ok;n9/1/202313数据结构与程序设计 9/1/202314数据结构与程序设计 Eight-Queens Puzzlenvoid print_information()nncoutThis is the Queens game.endl;n9/1/202315数据结构与程序设计 Eight-Queens Puzzle p188nvoid solve_from(Queens&configuration)n/*nUses:The class Queens and the function solve_from,recursively.n*/nn if(

9、configuration.is_solved()configuration.print();n elsen for(int col=0;col configuration.board_size;col+)n if(configuration.unguarded(col)n configuration.insert(col);n solve_from(configuration);/Recursively continue to add queens.n configuration.remove(col);n n9/1/202316数据结构与程序设计 Eight-Queens Puzzle p

10、186nvoid main()n/*nPre:The user enters a valid board size.nPost:All solutions to the n-queens puzzle for the selectedn board size are printed.nUses:The class Queens and the recursive function solve_from.n*/nn int board_size;n void solve_from(Queens&configuration);n void print_information();n print_i

11、nformation();n cout What is the size of the board?board_size;n if(board_size max_board)n cout The number must be between 0 and max_board endl;n else n Queens configuration(board_size);/Initialize empty configuration.n solve_from(configuration);/Find all solutions extending configuration.n n9/1/20231

12、7数据结构与程序设计 Eight-Queens PuzzlenP191nRefinement代码优化代码优化nP190 Figure 5.14(d),(e)n目录目录EightQueens2下例程下例程9/1/202318数据结构与程序设计 优化思路n（1）递归调用花费较多的时间和空间。但是优化的可能性不大，该问题有大量的解，需要多次递归。n（2）unguarded()函数的处理由三个循环组成，花费了较多时间，可以考虑是否进行优化。n基本思路是：优化数据存储结果，从而优化unguarded函数。9/1/202319数据结构与程序设计 9/1/202320数据结构与程序设计 Eight-Quee

13、ns Puzzle p193nconst int max_board=30;nclass Queens npublic:n Queens(int size);n bool is_solved()const;n void print()const;n bool unguarded(int col)const;n void insert(int col);n void remove(int col);n int board_size;/dimension of board=maximum number of queensnprivate:n int count;/current number of

14、 queens=first unoccupied rown bool col_freemax_board;n bool upward_free2*max_board-1;n bool downward_free2*max_board-1;n int queen_in_rowmax_board;/column number of queen in each rown;9/1/202321数据结构与程序设计 Eight-Queens PuzzlenQueens:Queens(int size)n/*nPost:The Queens object is set up as an emptyn con

15、figuration on a chessboard with size squares in each row and column.n*/nn board_size=size;n count=0;n for(int i=0;i board_size;i+)col_freei=true;n for(int j=0;j (2*board_size-1);j+)upward_freej=true;n for(int k=0;k (2*board_size-1);k+)downward_freek=true;n9/1/202322数据结构与程序设计 Eight-Queens Puzzlenbool

16、 Queens:unguarded(int col)constn/*nPost:Returns true or false according as the square in the firstn unoccupied row(row count)and column col is not guarded by any queen.n*/nn return col_freecoln&upward_freecount+coln&downward_freecount-col+board_size-1;n9/1/202323数据结构与程序设计 Eight-Queens Puzzlenvoid Qu

17、eens:insert(int col)n/*nPre:The square in the first unoccupied row(row count)and column coln is not guarded by any queen.nPost:A queen has been inserted into the square at row count and columnn col;count has been incremented by 1.n*/nn queen_in_rowcount=col;n col_freecol=false;n upward_freecount+col

18、=false;n downward_freecount-col+board_size-1=false;n count+;n9/1/202324数据结构与程序设计 Eight-Queens Puzzlenvoid Queens:remove(int col)nn count-;n col_freecol=true;n upward_freecount+col=true;n downward_freecount-col+board_size-1=true;n9/1/202325数据结构与程序设计 Eight-Queens Puzzlenvoid Queens:print()constnnint i

19、,j;nfor(i=0;iboard_size;i+)nnfor(j=0;jboard_size;j+)nn if(j=queen_in_rowi)cout 1 flush;n else cout 0 flush;nncout endl;nncoutendlendl;n9/1/202326数据结构与程序设计 Eight-Queens Puzzlenbool Queens:is_solved()constnn return(count=board_size);n9/1/202327数据结构与程序设计 Eight-Queens Puzzlen#includetime.hn cout What is

20、 the size of the board?board_size;n double start=time(NULL);n if(board_size max_board)n cout The number must be between 0 and max_board endl;n else n Queens configuration(board_size);/Initialize empty configuration.n solve_from(configuration);/Find all solutions extending configuration.n n double en

21、d=time(NULL);n coutIt takes time:(end-start)(s)endl;n/以上代码只能精确到秒以上代码只能精确到秒,没有办法打印出秒以后的差异。没有办法打印出秒以后的差异。9/1/202328数据结构与程序设计#includetime.hcout What is the size of the board?board_size;double start=clock();if(board_size max_board)cout The number must be between 0 and max_board endl;else Queens configur

22、ation(board_size);/Initialize empty configuration.solve_from(configuration);double end=clock();coutIt takes time:”(end-start)/CLOCKS_PER_SEC(s)endl;/以上代码只能精确到毫秒以上代码只能精确到毫秒9/1/202329数据结构与程序设计 Eight-Queens Puzzlen比较比较EightQueens和和EightQueens2的运行时的运行时间，注意注释间，注意注释print后比较。后比较。nBOOK P194-195分析回溯对工作量的减少。分

23、析回溯对工作量的减少。9/1/202330数据结构与程序设计 Eight-Queens Puzzlen上机作业上机作业 EightQueens29/1/202331数据结构与程序设计 Eight-Queens Puzzlen课后作业课后作业 nP196 E1,E2n已知已知Elements n为整数数组，试写出实现下列运算的递为整数数组，试写出实现下列运算的递归算法：归算法：(1)求数组求数组Elements中的最大整数。中的最大整数。int MaxKey(int Elements,int n)(2)求数组求数组Elements中中n个整数的和。个整数的和。int Sum(int Elements,int n)(3)求数组求数组Elements中中n个整数的平均值。个整数的平均值。float Average(int Elements,int n)9/1/202332数据结构与程序设计