四皇后问题的解空间树 四皇后问题的状态空间树上共有24个叶 结点(4!)就是问题的所有可能解, ■树的内部结点代表问题的部分解;例如 36为部分解(X1X2x3)=(312) ■结点的编号是按DFs( Deep First Search)方式排列的,其实也就是按回 溯方式遍历搜索的次序
16 四皇后问题的解空间树 ◼ 四皇后问题的状态空间树上共有24个叶 结点(4!),就是问题的所有可能解， ◼ 树的内部结点代表问题的部分解；例如 36为部分解(x1 ,x2 ,x3 )=(3,1,2) ◼ 结点的编号是按DFS（Deep First Search)方式排列的，其实也就是按回 溯方式遍历搜索的次序
搜索过程(1) 四皇后问题的 回溯算法的搜 索过程图示 从结点1到结 2 点2,满足条 18 件,放置皇后 x1=1继续向 前 13) 24 29 32=34 4 4 4 4(6(①(4202Q②0③ X 4 24 5⑦④①①⑦②②②Q8③③
17 搜索过程(1) ◼ 四皇后问题的 回溯算法的搜 索过程图示 ◼ 从结点1到结 点2，满足条 件，放置皇后 x1=1,继续向 前 1 X1=1 2 3 4 5 6 7 4 3 X2=2 8 9 10 2 4 11 12 4 2 3 13 14 15 2 3 16 17 3 2 4 2 18 19 20 21 3 4 22 23 4 3 1 24 25 26 1 4 27 28 4 1 3 29 30 31 1 3 32 33 3 1 4 X3=3 X4=4 Q
搜索过程(2) 结点3不满足 条件,回溯到 结点2 再向下搜索到 2 结点8;满足 18 条件,放置皇 后x2=3继续 向前 13) 24 29 32=34 4 4 4 4(6(①(4202Q②0③ X 4 24 5⑦④①④⑦②②②Q8③③ 18
18 搜索过程(2) ◼ 结点3不满足 条件，回溯到 结点2； ◼ 再向下搜索到 结点8；满足 条件，放置皇 后x2=3,继续 向前 1 X1=1 2 3 4 5 6 7 4 3 X2=2 8 9 10 2 4 11 12 4 2 3 13 14 15 2 3 16 17 3 2 4 2 18 19 20 21 3 4 22 23 4 3 1 24 25 26 1 4 27 28 4 1 3 29 30 31 1 3 32 33 3 1 4 X3=3 X4=4 Q X Q
搜索过程(3) 结点9不满足 条件,回溯到 结点8, 向下搜索到结 2 点11,不满足 18 条件,这时经 结点8,回溯 到结点2 13) 24 29 4 4 4 4(6(①(4202Q②0③ X 4 24 5⑦④①①⑦②②②Q8③③ 19
19 搜索过程(3) ◼ 结点9不满足 条件，回溯到 结点8， ◼ 向下搜索到结 点11，不满足 条件，这时经 结点8，回溯 到结点2 1 X1=1 2 3 4 5 6 7 4 3 X2=2 8 9 10 2 4 11 12 4 2 3 13 14 15 2 3 16 17 3 2 4 2 18 19 20 21 3 4 22 23 4 3 1 24 25 26 1 4 27 28 4 1 3 29 30 31 1 3 32 33 3 1 4 X3=3 X4=4 Q Q X X
搜索过程(4) 向下搜索到结 点13,满足条 件,放置第二 个皇后x2=4 2 继续向下搜索 18 到结点14满足 条件,放置第 三个皇后x3=2P 13) 24 29 4 4 4 6(④②②②Qg X 4 24 5⑦④①①⑦②②②Q8③③
20 搜索过程(4) ◼ 向下搜索到结 点13，满足条 件，放置第二 个皇后x2=4; ◼ 继续向下搜索 到结点14满足 条件，放置第 三个皇后x3=2; 1 X1=1 2 3 4 5 6 7 4 3 X2=2 8 9 10 2 4 11 12 4 2 3 13 14 15 2 3 16 17 3 2 4 2 18 19 20 21 3 4 22 23 4 3 1 24 25 26 1 4 27 28 4 1 3 29 30 31 1 3 32 33 3 1 4 X3=3 X4=4 Q Q Q