基本算法4-回溯法-N皇后问题.ppt

1、八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在88的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在nn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。,N皇后问题,44,4皇后问题的回溯举例 如何在44的方格棋盘上放置4个皇后，使它们互不攻击:,确定问题状态：问题的状态即棋盘的布局状态。 构造状态空间树：状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。 由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有n个子结点。,N

2、皇后问题,设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)，1xi4(i=1，2，3，4)，共4！个状态；,2,3,4,4,2,2,1,2,3,1,2,3,1,3,1,3,1,2,3,2,1,2,1,4,2,4,1,4,2,3,2,4,3,4,1,2,3,1,2,4,1,3,4,例：n=4的n皇后问题的搜索空间,5,47,55,4,11,27,46,48,52,54,59,3,8

3、,13,24,29,35,40,45,51,56,61,2,18,34,50,1,2,3,4,9,12,14,16,19,25,30,49,53,60,6,1,7,10,15,17,20,21,4,4,3,4,3,22,23,3,26,4,1,28,31,32,33,36,37,38,39,41,42,43,44,57,58,62,63,64,65,3,1,4,2,4,1,3,2,1,不同行：由于是一行只排一个皇后，所以肯定不同行。 不同列：设置一个数组：MARK0，当J列已安排皇后时，MARK0J:=FALSE。不允许再安排皇后。 不在同一对角线： *任意一条红色左斜线上的方格坐标都有一个规

4、律： 相等，只要标记MARK1I+J:=FALSE，该条红色左斜线都将不可安排。 红色的斜线从最左边11，2+1或1+2到NN条。 *任意一条绿色的右斜线上的方格坐标也有一个规律： 相等，也只要定义MARK2I-J=FALSE，则所有该右斜线都将不可安排。 绿色的斜线从最右边 1-N到N-1条。,最后的条件是： 当皇后准备安排在第 J列时，必须符合下列条件，才能安排： If MARK0J AND MARK1I+J and MARK2I-J Then Begin AI:=J； 安排皇后 MARK0J:=FALSE； MARK1I+J:=FALSE； MARK2I-J:=FALSE； 设置约束条件

5、，让其他皇后无法再放置 End；,约束条件,回溯：,当所有的J都不满足条件，第I+1个皇后无法安置时，此时应回溯第I个皇后，回溯如下： MARK0J:=TRUE： MARK1I+J:=TRUE： MARK2I-J:=TRUE 将第 I个皇后的约束条件释放，待重新安置后再确定约束条件。,加约束条件,搜索解空间，剪枝： (1) 从空棋盘起，逐行放置棋子。 (2) 每在一个布局中放下一个棋子，即推演到一个新的布局。 (3) 如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。,结点2变成E-结点, 它再生成结点3, 路径变为(1, 2), 即皇后1在第1列上,王后2在第2列上

6、, 所以结点3被杀死, 此时应回溯.,1,开始把根结点作为唯一的活结点, 根结点就成为E-结点而且路径为( ); 接着生成子结点, 假设按自然数递增的次序来生成子结点, 那么结点2被生成, 这条路径为(1), 即把皇后1放在第1列上.,kill,回溯到结点2生成结点8, 路径变为(1, 3), 则结点8成为E-结点, 它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格局), 所以结点8也被杀死, 应回溯.,kill,kill,回溯到结点2生成结点13, 路径变为(1, 4), 结点13成为E-结点, 由于它的儿子表示的是一些不可能导致答案结点的棋盘格局, 因此结点13也被杀

7、死, 应回溯,kill,kill,结点2的所有儿子表示的都是不可能导致答案的棋盘格局, 因此结点2也被杀死; 再回溯到结点1生成结点18, 路径变为(2).,kill,kill,结点18的子结点19、结点24被杀死, 应回溯.,结点18生成结点29, 结点29成为E-结点, 路径变为(2,4);,结点29生成结点30, 路径变为(2,4,1),结点30生成结点31, 路径变为(2,4,1,3), 找到一个4-王后问题的可行解,可行解,2,3,4,4,2,2,1,2,3,1,2,3,1,3,1,3,1,2,3,2,1,2,1,4,2,4,1,4,2,3,2,4,3,4,1,2,3,1,2,4,1

8、,3,4,n=4的n皇后问题的搜索、剪枝与回溯,5,47,55,4,11,27,46,48,52,54,59,3,8,13,24,29,35,40,45,51,56,61,2,18,34,50,1,2,3,4,9,12,14,16,19,25,30,49,53,60,6,1,7,10,15,17,20,21,4,4,3,4,3,22,23,3,26,4,1,28,31,32,33,36,37,38,39,41,42,43,44,57,58,62,63,64,65,3,1,4,2,4,1,3,2,1,参考程序段,Procedure try(I:Integer) ; Var j:integer;

9、Begin for j:=1 to N do IF 在J位置安排皇后不冲突，满足条件 then begin 确定A（I）=J，同时确定以后的约束条件 IF 不是最后一个皇后 THEN 递归调用 try(i+1) ELSE 打印结果； 如果I+1出了问题，应在此时回溯。上面的A（I）=J释放，由于递归时，自动记录了定位时的J值，所以在前面的J值后继续探索。 End; End;,program eightqueens; var x:array1.8 of integer; 当前8个皇后所摆的方案 a,b,c:array-7.16 of boolean; 分别是列，对角线，反对角线 i:intege

10、r; procedure print; 打印本次方案 var k:integer; begin for k:=1 to 8 do write(xk:4); writeln; end; procedure try(i:integer); 使用回溯法递归求解，试遍所有的情况，是一种递归枚举 var j:integer; begin for j:=1 to 8 do if aj and bi+j and ci-j then 若(i,j) 可放,begin xi:=j; 则第i行就放在第j列 aj:=false; 第j列不能放的标志 bi+j:=false; 左上-右下斜线不能放的标志 ci-j:=f

11、alse; 右上-左下斜线不能放的标志 if i8 then try(i+1)8个没放完，则继续放 else print; 放完去打印方案 aj:=true;回溯回来后，撤去不能放的标志 bi+j:=true; ci-j:=true end; end; begin for i:=-7 to 16 do初始化为每个位置均可放 begin ai:=true; bi:=true; ci:=true end; try(1);从第一行开始 end.,问题描述 学校放暑假时，信息学辅导教师有n本书要分给参加培训的n个学生。如：A，B，C，D，E共5本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选

12、1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。,借书问题,输入格式： 第一行一个数n（学生的个数，书的数量） 以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。 输出格式： 依次输出每个学生分到的书号。 输入样例：book.in 5 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 输出样例：book.out 3 1 2 4 5,分析: a:array1.100,1.100

13、of integer; /ai,j=1：第i个人喜欢第j本书，0表示不喜欢 b:array1.100 of integer; /记录分配方案:bi是第i个人借第bi本书 book:array 1.100 of 0.1; /booki=0:值为0表示可以借此本书，为1表示已经被他人借走，初始时值为0,一旦有人借，就改为1,算法设计: procedure work(i:integer);/要搜索第i个人可以借的书bi，说明:前i-1个人已经借好书 begin if (in) then sc();/输出结果； for j:=1 to n do/搜索第i个人能够借的书 if (bookj=0) and

14、 (ai,j=1) then /第i个人可以借第j 本书 begin bi:=j;/记录下第i个人借的书j bookj:=1;/标记第j本数已被借 work(i+1);/搜索第i+1个人可以借的书 bookj:=0;/删除书的被借标志;回溯时要消除当前作的标记，不影响下一次重新尝试 end; end;,program jieshu; var a:array1.100,1.100 of integer; ai,j=1:第i个人喜欢第j本书,0表示不喜欢 b,book:array1.100 of integer; bi是第i个人借第bi本书,booki值为0表示可以借此本书，为1表示已经被他人借走

15、 n:integer; procedure csh();读入原始数据 var i,j:integer; begin fillchar(b,sizeof(b),0); 所有人未借书 fillchar(book,sizeof(book),0); 所有书未借出 fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do begin for j:=1 to n do read(ai,j); readln; end; end;,procedure sc(); 打印最终结果 var i:integer; begin for i:=1 to n do write(bi, ); writeln; end;,procedure work(i:integer); 搜索第i个人可以借的书bi var j:integer; begin if (in) then s