program jieshu; var a:array[1..100,1..100] of integer; {a[i,j]=1:第i个人喜欢第j本书,0 表示不喜欢} b,book:array[1..100] of integer; {b[i]是第i个人借第b[i]本书 ,book[[i]值为0表示可以借此本书，为1表示已经被他人借走} 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(a[i,j]); readln; end; end;
61 2
64
3
16
3
20
4
22
1
25
4 1 27 1
30
4 1
38 41
9 11
4
43 46 48 52 54
57 59
62
2
3
15
2
17
4
21
3
23
4
26
3
1
4
2
39
4
42
1
44
2
1
2
3
3
58
1
60
2
63
1
65
5
10 12
28 31
33 37
47 49
53 55
参考程序段
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;
1 x1=1 2 x2= 4 x1= 2 18
1 3
1
x2= 1 x2= 4 x2= 3 29 24 13 19 8 3 x3=2 kill kill kill x3=4 x3=1 x3=2 x3=3 x2= 2 x2= 3
2
4 1 2 3 1 2
9 kill
11 14 kill x4=3 15 kill
● ●
……
● ● ● ● ● ● ● ●
……
……
●
●
●
●
●
● ● ● ●
●
●
● ●
●
● ●
●
● ●
● ● ● ●
● ● ● ●
● ● ● ●
● ● ● ● ●
● ● ●
•搜索解空间，剪枝：
– (1) 从空棋盘起，逐行放置棋子。
– (2) 每在一个布局中放下一个棋子，即推演到一 个新的布局。 – (3) 如果当前行上没有可合法放置棋子的位置， 则回溯到上一行，重新布放上一行的棋子。
18 x2= 4
1 1
2
x2= 1 x2 = 3 24 13 19 8 3 x3=2 kill kill kill x3=4 x3=2 x3=3 x2= 2 x2= 3 9 kill 11 14 kill x4=3 15 kill 16 kill
1 2
结点18生成结点29, 结点29成为E结点, 路径变为(2,4); 结点29生成结点30, 路径变为(2,4,1) 结点30生成结点31, 路 径变为(2,4,1,3), 找到一 个4-王后问题的可行解
输入格式： 第一行一个数n（学生的个数，书的数量） 以下共n行，每行n个0或1（由空格隔开），第I行数据表 示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜 欢该书。 输出格式： 依次输出每个学生分到的书号。 输入样例：book.in 5 00110 11000 01100 00010 01001 输出样例：book.out 31245
开始把根结点作为唯一的活结点, 根结点就成为E-结点 而且路径为( ); 接着生成子结点, 假设按自然数递增的次 序来生成子结点, 那么结点2被生成, 这条路径为(1), 即把 皇后1放在第1列上.
结点2变成E-结点, 它再生成结点3, 路径变为 (1, 2), 即皇后1在第1列上,王后2在第2列上, 所 以结点3被杀死, 此时应回溯.
不同行：由于是一行只排一个皇 后，所以肯定不同行。 不同列：设置一个数组：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条。
1
1
2
3
x2= 2 x2 = 3 3 kill 8 x3=2 9 kill
1
2
1 2 3
4
结点2的所有儿子表示的都是不可能 导致答案的棋盘格局, 因此结点2也被 杀死; 再回溯到结点1生成结点18, 路径 变为(2). 结点18的子结点19、结点 24被杀死, 应回溯.
1 x1=1 2 x1= 2
4×4
Q1 Q2 Q3 Q4

4皇后问题的回溯举例
如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击:
N皇后问题
• 确定问题状态：问题的状态即棋盘的布局状态。
• 构造状态空间树：状态空间树的根为空棋盘，每个布局 的下一步可能布局是该布局结点的子结点。
– 由于可以预知，在每行中有且只有一个皇后，因此可 采用逐行布局的方式，即每个布局有n个子结点。
回溯：
当所有的J都不满足条件，第I+1个皇后无法安置时，此 时应回溯第I个皇后，回溯如下： MARK0[J]:=TRUE： MARK1[I+J]:=TRUE： MARK2[I-J]:=TRUE 将第 I个皇后的约束条件释放，待重新安置后再确定约 束条件。
加约束条件
● ● ● ●
● ●
● ●
ห้องสมุดไป่ตู้
● ●
1
x1=1 2
x2= 2 3 kill
1
1 2
回溯到结点2生成结点8, 路径变为(1, 3), 则结点8成为E-结点, 它生成结点9和结点11都会被杀死(即它的儿子表示不可能导 x1=1 致答案的棋盘格局), 所以结点8也被杀死, 应回溯.
1
1
1
2
2
3
x2= 2 x2= 3 3 kill 8 x3=2 9 kill x3=4 11 kill
16 kill
30 x4=3 31
可 行 解
n=4的n皇后问题的搜索、剪枝与回溯
1
2 2 2 3 3 3 4 4 4 2 6 3 7 8 4 2
14 13 19 18
1 3 34 4
29
4
50 4 45 4 1 2 3 51 2 1 1 3
4
1
3 24
1 35 3 2
32 36
2 40
2 56
3 1
1
2
1 2 3
回溯到结点2生成结点13, 路径变为(1, 4), 结点13成 为E-结点, 由于它的儿子表示的是一些不可能导致答 案结点的棋盘格局, 因此结点13也被杀死, 应回溯
1 x1=1 2 x2= 4 13 x3=2 x3=4 x3=3 11 14 kill x4=3 15 kill 16 kill
• 设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！个状态；
算法设计: procedure work(i:integer);//要搜索第i个人可以借的书b[i]，说明:前 i-1个人已经借好书 begin if (i>n) then sc();//输出结果； for j:=1 to n do//搜索第i个人能够借的书 if (book[j]=0) and (a[i,j]=1) then //第i个人可以借第j 本书 begin b[i]:=j;//记录下第i个人借的书j book[j]:=1;//标记第j本数已被借 work(i+1);//搜索第i+1个人可以借的书 book[j]:=0;//删除书的被借标志;回溯时要消除当前作的标 记，不影响下一次重新尝试 end; end;
1
62
2
64
9 11
4 2
27
1
30
43 46 48 52 54
57 59
4
5
3
15
2
17
4
21
3
23
4
26
3
1
4
2
39
4
42
1
44
2
1
2
3
3
58
1