基本算法4-回溯法-N皇后问题概要

Q1Q2Q3Q4八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。N皇后问题4×44皇后问题的回溯举例如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击:•确定问题状态：问题的状态即棋盘的布局状态。•构造状态空间树：状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。–由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有n个子结点。N皇后问题•设4个皇后为xi，分别在第i行(i=1，2，3，4)；•问题的解状态：可以用(1,x1)，(2,x2)，……，(4,x4)表示4个皇后的位置；–由于行号固定，可简单记为：(x1,x2,x3,x4)；–例如：(4,2,1,3)•问题的解空间：(x1,x2,x3,x4)，1≤xi≤4(i=1，2，3，4)，共4！个状态；2344221231231313123212142414232434123124134例：n=4的n皇后问题的搜索空间5475541127464852545938132429354045515661218345012349121416192530495360617101517202144343222332641283132333637383941424344575862636465314241321不同行：由于是一行只排一个皇后，所以肯定不同行。不同列：设置一个数组：MARK0，当J列已安排皇后时，MARK0[J]:=FALSE。不允许再安排皇后。不在同一对角线：*任意一条红色左斜线上的方格坐标都有一个规律：Ｉ＋Ｊ相等，只要标记MARK1[I+J]:=FALSE，该条红色左斜线都将不可安排。红色的斜线从最左边1＋1，2+1或1+2到N＋N条。*任意一条绿色的右斜线上的方格坐标也有一个规律：Ｉ－Ｊ相等，也只要定义MARK2[I-J]=FALSE，则所有该右斜线都将不可安排。绿色的斜线从最右边1-N到N-1条。最后的条件是：当皇后准备安排在第J列时，必须符合下列条件，才能安排：IfMARK0[J]ANDMARK1[I+J]andMARK2[I-J]ThenBeginA[I]:=J；安排皇后MARK0[J]:=FALSE；MARK1[I+J]:=FALSE；MARK2[I-J]:=FALSE；{设置约束条件，让其他皇后无法再放置}End；约束条件回溯：当所有的J都不满足条件，第I+1个皇后无法安置时，此时应回溯第I个皇后，回溯如下：MARK0[J]:=TRUE：MARK1[I+J]:=TRUE：MARK2[I-J]:=TRUE将第I个皇后的约束条件释放，待重新安置后再确定约束条件。加约束条件●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●•搜索解空间，剪枝：–(1)从空棋盘起，逐行放置棋子。–(2)每在一个布局中放下一个棋子，即推演到一个新的布局。–(3)如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。结点2变成E-结点,它再生成结点3,路径变为(1,2),即皇后1在第1列上,王后2在第2列上,所以结点3被杀死,此时应回溯.13x2=22x1=1开始把根结点作为唯一的活结点,根结点就成为E-结点而且路径为();接着生成子结点,假设按自然数递增的次序来生成子结点,那么结点2被生成,这条路径为(1),即把皇后1放在第1列上.kill1128x2=3回溯到结点2生成结点8,路径变为(1,3),则结点8成为E-结点,它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格局),所以结点8也被杀死,应回溯.13x2=22x1=1kill11x3=49x3=2112123killkill12313x2=415x4=3回溯到结点2生成结点13,路径变为(1,4),结点13成为E-结点,由于它的儿子表示的是一些不可能导致答案结点的棋盘格局,因此结点13也被杀死,应回溯8x2=313x2=22x1=1kill11x3=49x3=2killkill14x3=2kill112123412316x3=3kill18x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill结点2的所有儿子表示的都是不可能导致答案的棋盘格局,因此结点2也被杀死;再回溯到结点1生成结点18,路径变为(2).19x2=124x2=3killkill结点18的子结点19、结点24被杀死,应回溯.11212131x4=3结点18生成结点29,结点29成为E-结点,路径变为(2,4);18x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill19x2=124x2=3killkill121231234结点29生成结点30,路径变为(2,4,1)结点30生成结点31,路径变为(2,4,1,3),找到一个4-王后问题的可行解29x2=430x3=1可行解2344221231231313123212142414232434123124134n=4的n皇后问题的搜索、剪枝与回溯5475541127464852545938132429354045515661218345012349121416192530495360617101517202144343222332641283132333637383941424344575862636465314241321参考程序段Proceduretry(I:Integer);Varj:integer;Beginforj:=1toNdoIF在J位置安排皇后不冲突，满足条件thenbegin确定A（I）=J，同时确定以后的约束条件IF不是最后一个皇后THEN递归调用try(i+1)ELSE打印结果；如果I+1出了问题，应在此时回溯。上面的A（I）=J释放，由于递归时，自动记录了定位时的J值，所以在前面的J值后继续探索。End;End;programeightqueens;varx:array[1..8]ofinteger;{当前8个皇后所摆的方案}a,b,c:array[-7..16]ofboolean;{分别是列，对角线，反对角线}i:integer;procedureprint;{打印本次方案}vark:integer;beginfork:=1to8dowrite(x[k]:4);writeln;end;proceduretry(i:integer);{使用回溯法递归求解，试遍所有的情况，是一种递归枚举}varj:integer;beginforj:=1to8doifa[j]andb[i+j]andc[i-j]then{若(i,j)可放}beginx[i]:=j;{则第i行就放在第j列}a[j]:=false;{第j列不能放的标志}b[i+j]:=false;{左上-右下斜线不能放的标志}c[i-j]:=false;{右上-左下斜线不能放的标志}ifi8thentry(i+1){8个没放完，则继续放}elseprint;{放完去打印方案}a[j]:=true;{回溯回来后，撤去不能放的标志}b[i+j]:=true;c[i-j]:=trueend;end;beginfori:=-7to16do{初始化为每个位置均可放}begina[i]:=true;b[i]:=true;c[i]:=trueend;try(1);{从第一行开始}end.[问题描述]学校放暑假时，信息学辅导教师有n本书要分给参加培训的n个学生。如：A，B，C，D，E共5本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。ABCDE张YY王YY刘YY孙Y李YY借书问题输入格式：第一行一个数n（学生的个数，书的数量）以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号。输入样例：book.in50011011000011000001001001输出样例：book.out31245分析:a:array[1..100,1..100]ofinteger;//a[i,j]==1：第i个人喜欢第j本书，0表示不喜欢b:array[1..100]ofinteger;//记录分配方案:b[i]是第i个人借第b[i]本书book:array[1..100]of0..1;//book[[i]=0:值为0表示可以借此本书，为1表示已经被他人借走，初始时值为0,一旦有人借，就改为1算法设计:procedurework(i:integer);//要搜索第i个人可以借的书b[i]，说明:前i-1个人已经借好书beginif(in)thensc();//输出结果；forj:=1tondo//搜索第i个人能够借的书if(book[j]=0)and(a[i,j]=1)then//第i个人可以借第j本书beginb[i]:=j;//记录下第i个人借的书jbook[j]:=1;//标记第j本数已被借work(i+1);//搜索第i+1个人可以借的书book[j]:=0;//删除书的被借标志;回溯时要消除当前作的标记，不影响下一次重新尝试end;end;programjieshu;vara:array[1..100,1..100]ofinteger;{a[i,j]=1:第i个人喜欢第j本书,0表示不喜欢}b,book:array[1..100]ofinteger;{b[i]是第i个人借第b[i]本书,book[[i]值为0表示可以借此本书，为1表示已经被他人借走}n:integer;procedurecsh();{读入原始数据}vari,j:integer;beginfillchar(b,sizeof(b),0);{所有人未借书}fillchar(book,sizeof(book),0);{所有书未借出}fillchar(a,sizeof(a),0);readln(n);fori:=1tondobeginforj:=1tondoread(a[i,j]);readln;end;end;proceduresc();{打印最终结果}vari:integer;beginfori:=1tondowrite(b[i],'');writeln;end;procedurework(i:integer);{搜索第i个人可以借的书b[i]}varj:integer;beginif(in)thensc();{边界条件满足,输出结果}forj:=1tondo{搜索第i个人能够借的书}if(book[j]=0)and(a[i,j]=1)then{第i个人可以借第j本书}beginb[i]:=j;{记录下第i个人借的书j}book[j]:=1;{标记第j本数已被借}work(i+1);{搜索第i+1个人可以借的书}book[j]:=0;{删除书的被借标志,回溯}end;end;begincsh();work(1);end.