基本算法回溯法N皇后问题.pptVIP

回溯： 　 当所有的J都不满足条件，第I+1个皇后无法安置时，此时应回溯第I个皇后，回溯如下： 　　 MARK0[J]:=TRUE： MARK1[I+J]:=TRUE： MARK2[I-J]:=TRUE 　　将第 I个皇后的约束条件释放，待重新安置后再确定约束条件。 参考程序段 　 Procedure try(I:Integer) ; 　　 Var j:integer; 　　 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:array[1..8] of integer; {当前8个皇后所摆的方案} a,b,c:array[-7..16] of boolean; {分别是列，对角线，反对角线} i:integer; procedure print; {打印本次方案} var k:integer; begin for k:=1 to 8 do write(x[k]:4); writeln; end; procedure try(i:integer); {使用回溯法递归求解，试遍所有的情况，是一种递归枚举} var j:integer; begin for j:=1 to 8 do if a[j] and b[i+j] and c[i-j] then {若(i,j) 可放} * * Q4 Q3 Q2 Q1 八皇后问题是十九世纪著名的数学家高斯于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！个状态； 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 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列已安排皇后时，MARK0[J]:=FALSE。不允许再安排皇后。 不在同一对角线： *任意一条红色左斜线上的方格坐标都有一个规律： Ｉ＋Ｊ相等，只要标记MARK1[I+J]:=FALSE，该条红色左斜线都将不可安排。　　 红色的斜线从最左边1＋1，2+1或1+2到N＋N条。 *任意一条绿色的右斜线上的方格坐标也有一个规律： Ｉ－Ｊ相等，也只要定义MARK2[I-J]=FALSE，则所有该右斜线都将不可安排。 　　 绿色的斜线从最右边 1-N到N-1条。 最后的条件是： 当皇后准备安排在第 J列时，必须符合下列条