递-归-算-法-举-例-八皇后问题课件.ppt

1、h1递递 归归 算算 法法 举举 例例八皇后问题八皇后问题h2 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8h3 在在88的棋盘上，放置的棋盘上，放置8个皇后（棋子），使个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：皇后都要满足：（1）不在棋盘的同一行；）不在棋盘的同一行；（2）不在棋盘的同一列；）不在棋盘的同一列；（3）不在棋盘的同一对角线上。）不在棋盘的同一对角线上。因此可以推论出，棋盘共有因此可以推论出，棋盘共有8行，每行有且仅行，每行有且仅有一个皇后，故至多有有一个皇后，故至多有8个皇后。这个皇后。

2、这8个皇后每个个皇后每个应该放在哪一列上是解该题的任务。我们还是用应该放在哪一列上是解该题的任务。我们还是用试探的方法试探的方法“向前走，碰壁回头向前走，碰壁回头”的策略。这就的策略。这就是是“回溯法回溯法”的解题思路。的解题思路。h4 1、定义、定义Try(i)试探放第试探放第 i 行上的皇后。行上的皇后。2、讨论将第、讨论将第 i 行上的皇后放在行上的皇后放在 j 列位置上的安列位置上的安全性。我们可以逐行地放每一个皇后，因此，在全性。我们可以逐行地放每一个皇后，因此，在做这一步时，假定第做这一步时，假定第 i 行上还没有皇后，不会在行行上还没有皇后，不会在行上遭到其它皇后的攻击。只考虑来

3、自列和对角线上遭到其它皇后的攻击。只考虑来自列和对角线的攻击。我们定义的攻击。我们定义 q(i)=j 表示第表示第 i 行上的皇后行上的皇后放在第放在第 j 列，一旦这样做了，就要考虑第列，一旦这样做了，就要考虑第 i 个皇后个皇后所在的列不安全了，这时让所在的列不安全了，这时让 C j=false，同时，同时，要考虑通过要考虑通过(i,j)位置的两条对角线也不安全了。位置的两条对角线也不安全了。分析看出从左上到右下的对角线上的每个位置都分析看出从左上到右下的对角线上的每个位置都有有 i j=常数常数 的特点；从左下到右上的对角的特点；从左下到右上的对角线上的每个位置都有线上的每个位置都有 i

4、+j=常数常数 的特点。的特点。h5h6h7 h8 h9 h10 h11 h12h13h14h15h16h17h18h19h20h21h22/*/*程程 序：序：6_9.cpp */*作作 者：者：wuwh */*编制时间：编制时间：2006年年2月月26日日 */*主要功能：主要功能：四皇后问题四皇后问题 */*#include/预编译命令预编译命令using namespace std;const int Normalize=5;/定义常量，用来统一数组下标定义常量，用来统一数组下标int Num=1;/整型变量，记录方案数整型变量，记录方案数int q5;/记录记录4个皇后所占用的列号个

5、皇后所占用的列号bool C5;/C1C4，布尔型变量，当前列是否安全，布尔型变量，当前列是否安全bool L9;/L2L8，布尔型变量，布尔型变量，(i-j)对角线是否安全对角线是否安全bool R9;/R2R8，布尔型变量，布尔型变量，(i+j)对角线是否安全对角线是否安全h23h24qi=j;/第一件事，占用位置第一件事，占用位置(i,j)Cj=false;/修改安全标志，包括所在列和两个对角线修改安全标志，包括所在列和两个对角线 Li-j+Normalize=false;Ri+j=false;if(i4)/第二件事，判断是否放完第二件事，判断是否放完8个皇后个皇后 /未放完未放完8个皇

6、后个皇后Try(i+1);/则继续放下一个则继续放下一个 else /已经放完已经放完4个皇后个皇后 Num+;/方案数加方案数加1cout 方案方案 Num ：;/输出方案号输出方案号for(k=1;k=4;k+)cout qk ;/输出具体方案输出具体方案cout endl;/换行换行 Cj=true;/第三件事，修改安全标志，回溯第三件事，修改安全标志，回溯Li-j+Normalize=true;Ri+j=true;h25/循环结束循环结束/Try函数结束函数结束int main()/主函数主函数int i;/循环变量循环变量Num=0;/方案数清零方案数清零for(i=1;i5;i+)

7、/置所有列为安全置所有列为安全Ci=true;for(i=0;i9;i+)/置所有对角线为安全置所有对角线为安全Li=Ri=true;Try(1);/递归放置递归放置4个皇后，从第一个开始放个皇后，从第一个开始放 return 0;h26h27h28h29h30h31h32h33利用这个特点，我们可以令利用这个特点，我们可以令L i-j+9 =false;R i+j =false;来表示在来表示在(i,j)位置放皇后之后，通过该位置的两条位置放皇后之后，通过该位置的两条对角线上不安全了。对角线上不安全了。这样我们得出了在这样我们得出了在(i,j)位置放皇后的安全条件为位置放皇后的安全条件为nq

8、=C j&L i-j+9&R i+j h34h35为了判断安全条件，在程序中要用到三个数组为了判断安全条件，在程序中要用到三个数组（1）C j 为布尔型的，为布尔型的，j=1,2,8，初始化时全部，初始化时全部 置为置为 true；（2）L k 为布尔型的，为布尔型的，k=i-j+9,k=2,3,16,初始化时全部置为初始化时全部置为 true；（3）R m 为布尔型的为布尔型的,m=i+j,m=2,3,16，初始化时全部置为初始化时全部置为 true；h363、从思路上，在放第、从思路上，在放第 i 个皇后时（当然在第个皇后时（当然在第 i行），行），选第选第 j 列，当列，当 nq 为为

9、true 时，就可将皇后放在时，就可将皇后放在(i,j)位置，这时做如下位置，这时做如下 3 件事件事（1）放皇后）放皇后q i =j，同时让第，同时让第 j 列和过列和过(i,j)位位置的两条对角线变为不安全。即让置的两条对角线变为不安全。即让C j =false;L i-j+9=false;R i+j =false;h37（2）之后查一下）之后查一下 i 是否为是否为 8，如果为，如果为8，则表明已经放完，则表明已经放完8个皇个皇后，这时让方案数后，这时让方案数 Num 加加 1，输出该方案下，输出该方案下 8个皇后在棋个皇后在棋盘上的位置。否则，未到盘上的位置。否则，未到 8个，还要让皇

10、后数个，还要让皇后数 i 加加 1 再试着再试着放，这时还要递归调用放，这时还要递归调用 Try(i+1)。（3）回溯，将先前放的皇后从棋盘上拿起来，看看还有没有）回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可能换一处放置。这时要将被拿起来的皇后的所在位置的可能换一处放置。这时要将被拿起来的皇后的所在位置的第第 j列，和两条对角线恢复为安全的。我们用与或图来描述列，和两条对角线恢复为安全的。我们用与或图来描述 8皇后问题的解题思路。皇后问题的解题思路。h38Try(i+1)Try(i+1)A Try(i)不安全不安全8j=12LpLpLpNum+;输出一个棋局输出一个棋局什么也不做什么也不

11、做安全安全i=8i8Cj=true;Li-j=true;Ri+j=true;qi=j;Cj=false;Li-j=false;Ri+j=false;h39h40h41h42/*/*程程 序：序：6_9.cpp */*作作 者：者：wuwh */*编制时间：编制时间：2002年年11月月06日日 */*主要功能：八皇后问题主要功能：八皇后问题 */*#include/预编译命令预编译命令using namespace std;const int Normalize=9;/定义常量，用来统一数组下标定义常量，用来统一数组下标int Num=0;/整型变量，记录方案数整型变量，记录方案数int q9

12、;/记录记录8个皇后所占用的列号个皇后所占用的列号bool C9;/C1C8，布尔型变量，当前列是否安全，布尔型变量，当前列是否安全bool L17;/L2L16，布尔型变量，布尔型变量，(i-j)对角线是否安全对角线是否安全bool R17;/R2R16，布尔型变量，布尔型变量，(i+j)对角线是否安全对角线是否安全h43h44qi=j;/第一件事，占用位置第一件事，占用位置(i,j)Cj=false;/修改安全标志，包括所在列和两个对角线修改安全标志，包括所在列和两个对角线 Li-j+Normalize=false;Ri+j=false;if(i8)/第二件事，判断是否放完第二件事，判断是

13、否放完8个皇后个皇后 /未放完未放完8个皇后个皇后Try(i+1);/则继续放下一个则继续放下一个 else /已经放完已经放完8个皇后个皇后 Num+;/方案数加方案数加1cout 方案方案 Num ：;/输出方案号输出方案号for(k=1;k=8;k+)cout qk ;/输出具体方案输出具体方案cout endl;/换行换行 Cj=true;/第三件事，修改安全标志，回溯第三件事，修改安全标志，回溯Li-j+Normalize=true;Ri+j=true;h45/循环结束循环结束/Try函数结束函数结束int main()/主函数主函数int i;/循环变量循环变量Num=0;/方案数

14、清零方案数清零for(i=0;i9;i+)/置所有列为安全置所有列为安全Ci=true;for(i=0;i17;i+)/置所有对角线为安全置所有对角线为安全Li=Ri=true;Try(1);/递归放置递归放置8个皇后，从第一个开始放个皇后，从第一个开始放 return 0;h46共共92组解，部分答案如下：组解，部分答案如下：方案方案1：1 5 8 6 3 7 2 4方案方案2：1 6 8 3 7 4 2 5方案方案3：1 7 4 6 8 2 5 3方案方案4：1 7 5 8 2 4 6 3方案方案5：2 4 6 8 3 1 7 5方案方案6：2 5 7 1 3 8 6 4方案方案7：2 5 7 4 1 8 6 3方案方案8：2 6 1 7 4 8 3 5方案方案9：2 6 8 3 1 4 7 5方案方案10：2 7 3 6 8 5 1 4h47结结 束束