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

2 20 2020 数据结构与程序设计 1 数据结构与程序设计 12 王丽苹lipingwang 2 20 2020 数据结构与程序设计 2 Eight QueensPuzzle BookP183 184 2 20 2020 数据结构与程序设计 3 Four Queenssolution 2 20 2020 数据结构与程序设计 4 Four Queenssolution 2 20 2020 数据结构与程序设计 5 ProgramOutline 2 20 2020 数据结构与程序设计 6 Eight QueensPuzzle 目录EightQueens下例程 2 20 2020 数据结构与程序设计 7 Eight QueensPuzzle constintmax board 30 classQueens public Queens intsize boolis solved const voidprint const boolunguarded intcol const voidinsert intcol voidremove intcol intboard size dimensionofboard maximumnumberofqueensprivate intcount currentnumberofqueens firstunoccupiedrowboolqueen square max board max board 2 20 2020 数据结构与程序设计 8 Eight QueensPuzzle boolQueens is solved const return count board size 2 20 2020 数据结构与程序设计 9 Eight QueensPuzzle voidQueens print const inti j for i 0 i board size i for j 0 j board size j cout queen square i j flush cout endl cout endl endl 2 20 2020 数据结构与程序设计 10 Eight QueensPuzzle voidQueens remove intcol queen square count col false 2 20 2020 数据结构与程序设计 11 Eight QueensPuzzle voidQueens insert intcol Pre Thesquareinthefirstunoccupiedrow rowcount andcolumncolisnotguardedbyanyqueen Post Aqueenhasbeeninsertedintothesquareatrowcountandcolumncol counthasbeenincrementedby1 queen square count col true 2 20 2020 数据结构与程序设计 12 Eight QueensPuzzle Queens Queens intsize Post TheQueensobjectissetupasanemptyconfigurationonachessboardwithsizesquaresineachrowandcolumn board size size count 0 for introw 0 row board size row for intcol 0 col board size col queen square row col false 2 20 2020 数据结构与程序设计 13 Eight QueensPuzzlep191 boolQueens unguarded intcol const Post Returnstrueorfalseaccordingasthesquareinthefirstunoccupiedrow rowcount andcolumncolisnotguardedbyanyqueen inti boolok true turnsfalseifwefindaqueenincolumnordiagonalfor i 0 ok 2 20 2020 数据结构与程序设计 14 2 20 2020 数据结构与程序设计 15 Eight QueensPuzzle voidprint information cout ThisistheQueensgame endl 2 20 2020 数据结构与程序设计 16 Eight QueensPuzzlep188 voidsolve from Queens 2 20 2020 数据结构与程序设计 17 Eight QueensPuzzlep186 voidmain Pre Theuserentersavalidboardsize Post Allsolutionstothen queenspuzzlefortheselectedboardsizeareprinted Uses TheclassQueensandtherecursivefunctionsolve from intboard size voidsolve from Queens Findallsolutionsextendingconfiguration 2 20 2020 数据结构与程序设计 18 Eight QueensPuzzle P191Refinement 代码优化P190Figure5 14 d e 目录EightQueens2下例程 2 20 2020 数据结构与程序设计 19 优化思路 1 递归调用花费较多的时间和空间 但是优化的可能性不大 该问题有大量的解 需要多次递归 2 unguarded 函数的处理由三个循环组成 花费了较多时间 可以考虑是否进行优化 基本思路是 优化数据存储结果 从而优化unguarded函数 2 20 2020 数据结构与程序设计 20 2 20 2020 数据结构与程序设计 21 Eight QueensPuzzlep193 constintmax board 30 classQueens public Queens intsize boolis solved const voidprint const boolunguarded intcol const voidinsert intcol voidremove intcol intboard size dimensionofboard maximumnumberofqueensprivate intcount currentnumberofqueens firstunoccupiedrowboolcol free max board boolupward free 2 max board 1 booldownward free 2 max board 1 intqueen in row max board columnnumberofqueenineachrow 2 20 2020 数据结构与程序设计 22 Eight QueensPuzzle Queens Queens intsize Post TheQueensobjectissetupasanemptyconfigurationonachessboardwithsizesquaresineachrowandcolumn board size size count 0 for inti 0 i board size i col free i true for intj 0 j 2 board size 1 j upward free j true for intk 0 k 2 board size 1 k downward free k true 2 20 2020 数据结构与程序设计 23 Eight QueensPuzzle boolQueens unguarded intcol const Post Returnstrueorfalseaccordingasthesquareinthefirstunoccupiedrow rowcount andcolumncolisnotguardedbyanyqueen returncol free col 2 20 2020 数据结构与程序设计 24 Eight QueensPuzzle voidQueens insert intcol Pre Thesquareinthefirstunoccupiedrow rowcount andcolumncolisnotguardedbyanyqueen Post Aqueenhasbeeninsertedintothesquareatrowcountandcolumncol counthasbeenincrementedby1 queen in row count col col free col false upward free count col false downward free count col board size 1 false count 2 20 2020 数据结构与程序设计 25 Eight QueensPuzzle voidQueens remove intcol count col free col true upward free count col true downward free count col board size 1 true 2 20 2020 数据结构与程序设计 26 Eight QueensPuzzle voidQueens print const inti j for i 0 i board size i for j 0 j board size j if j queen in row i cout 1 flush elsecout 0 flush cout endl cout endl endl 2 20 2020 数据结构与程序设计 27 Eight QueensPuzzle boolQueens is solved const return count board size 2 20 2020 数据结构与程序设计 28 Eight QueensPuzzle include time h cout board size doublestart time NULL if board sizemax board cout Thenumbermustbebetween0and max board endl else Queensconfiguration board size Initializeemptyconfiguration solve from configuration Findallsolutionsextendingconfiguration doubleend time NULL cout Ittakestime end start s endl 以上代码只能精确到秒 没有办法打印出秒以后的差异 2 20 2020 数据结构与程序设计 29 include time h cout board size doublestart clock if board sizemax board cout Thenumbermustbebetween0and max board endl else Queensconfiguration board size Initializeemptyconfiguration solve from configuration doubleend clock cout Ittakestime end start CLOCKS PER SEC s endl 以上代码只能精确到毫秒 2 20 2020 数据结构与程序设计 30 Eight QueensPuzzle 比较EightQueens和EightQueens2的运行时间 注意注释print后比较 BOOKP194 195分析回溯对工作量的减少 2 20 2020 数据结构与程序设计 31 E