回溯法求解N皇后问题

1、AlgorithmHHIT8.1.3 回溯法的求解过程回溯法的求解过程 由于问题的解向量由于问题的解向量X=(x1, x2, , xn)中的每个分量中的每个分量xi(1in)都属于一个有限集合都属于一个有限集合Si=ai1, ai2, , airi，因此，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积积S1S2Sn中的元素。中的元素。 初始时，令解向量初始时，令解向量X为空，然后，从根结点出发，选为空，然后，从根结点出发，选择择S1的第一个元素作为解向量的第一个元素作为解向量X的第一个分量，即的第一个分量，即x1= a11，如果如果X=

2、(x1)是问题的部分解，则继续扩展解向量是问题的部分解，则继续扩展解向量X，选择，选择S2的第一个元素作为解向量的第一个元素作为解向量X的第的第2个分量，否则，选择个分量，否则，选择S1的下一个元素作为解向量的下一个元素作为解向量X的第一个分量，即的第一个分量，即x1= a12。依此类推，一般情况下，如果依此类推，一般情况下，如果X=(x1, x2, , xi)是问题的部是问题的部分解，则选择分解，则选择Si+1的第一个元素作为解向量的第一个元素作为解向量X的第的第i+1个分个分量时，有下面三种情况：量时，有下面三种情况：AlgorithmHHIT（1）如果）如果X=(x1, x2, , xi

3、1)是问题的是问题的最终解最终解，则输出这个解。，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；他解；（2）如果）如果X=(x1, x2, , xi1)是问题的是问题的部分解部分解，则继续构造解，则继续构造解向量的下一个分量；向量的下一个分量；（3）如果）如果X=(x1, x2, , xi1)既不是问题的部分解也不是问题既不是问题的部分解也不是问题的最终解，则存在下面两种情况：的最终解，则存在下面两种情况： 如果如果xi+1= ai1k不是集合不是集合Si1的最后一个元素，则令的最后一个元素，则令xi+1= ai1k

4、1，即选择，即选择Si+1的下一个元素作为解向量的下一个元素作为解向量X的第的第i+1个分量；个分量； 如果如果xi+1= ai1k是集合是集合Si1的最后一个元素，就回溯到的最后一个元素，就回溯到X=(x1, x2, , xi)，选择，选择Si的下一个元素作为解向量的下一个元素作为解向量X的第的第i个分量，假个分量，假设设xi= aik，如果，如果aik不是集合不是集合Si的最后一个元素，则令的最后一个元素，则令xi= aik1；否则，就继续回溯到否则，就继续回溯到X=(x1, x2, , xi1)；AlgorithmHHIT8.3.1 八皇后问题八皇后问题 八皇后问题是十九世纪著名的数学家

5、高斯于八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在年提出的。问题是：在88的棋盘上摆放八的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都个皇后，使其不能互相攻击，即任意两个皇后都不能处于不能处于同一行、同一列或同一斜线上同一行、同一列或同一斜线上。可以把。可以把八皇后问题扩展到八皇后问题扩展到n皇后问题，即在皇后问题，即在nn的棋盘的棋盘上摆放上摆放n个皇后，使任意两个皇后都不能处于同个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。一行、同一列或同一斜线上。AlgorithmHHIT 若两个皇后摆放的位置分别是若两个皇后摆放的位置分别是(i, xi)和

6、和(j, xj)，在棋盘，在棋盘上斜率为上斜率为-1的斜线上，满足条件的斜线上，满足条件ij= xjxi ，在棋盘上斜，在棋盘上斜率为率为1的斜线上，满足条件的斜线上，满足条件ij= xixj，综合两种情况，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量由于两个皇后不能位于同一斜线上，所以，解向量X必须必须满足约束条件：满足约束条件： | |i j | | | xi xj| | （式（式8.2） 显然，棋盘的每一行上可以而且必须摆放一个皇后，显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，所以，n皇后问题的可能解用一个皇后问题的可能解用一个n元向量元向量X=(x1, x2, ,

7、 xn)表示，其中，表示，其中，1in并且并且1xin，即第，即第i个皇后放在第个皇后放在第i行第行第xi列上。列上。 由于两个皇后不能位于同一列上，所以，解向量由于两个皇后不能位于同一列上，所以，解向量X必必须满足约束条件：须满足约束条件： xixj （式（式8.1）AlgorithmHHIT1 2 3 41234皇后1皇后2皇后3皇后4图8.11 四皇后问题 为了简化问题，下面讨论四皇后问题。为了简化问题，下面讨论四皇后问题。 四皇后问题的解空间树是一个完全四皇后问题的解空间树是一个完全4叉树，树的根结叉树，树的根结点表示搜索的初始状态，从根结点到第点表示搜索的初始状态，从根结点到第2层结

8、点对应皇后层结点对应皇后1在棋盘中第在棋盘中第1行的可能摆放位置，从第行的可能摆放位置，从第2层结点到第层结点到第3层结层结点对应皇后点对应皇后2在棋盘中第在棋盘中第2行的可能摆放位置，依此类推。行的可能摆放位置，依此类推。AlgorithmHHITQQ QQ Q QQQQ Q QQ QQQQQQQ Q(a) (b) (c) (d) (e)(f) (g) (h) (i) (j)QQ Q回溯法求解回溯法求解4皇后问题的搜索过程皇后问题的搜索过程AlgorithmHHIT算法的实现 假设回溯法要找出所有的答案结点假设回溯法要找出所有的答案结点 。 设设(x1,x2,xi-1)是状态空间树中由根到一

9、个结是状态空间树中由根到一个结点的路径，而点的路径，而T(x1,xi-1)是下述所有结点是下述所有结点xi的的集合，它使得对于每一个集合，它使得对于每一个xi，(x1,x2,xi)是由是由根到一个结点根到一个结点xi的路径；假定还存在着一些的路径；假定还存在着一些限限界函数界函数Bi，如果路径，如果路径(x1,x2,xi)不可能延伸到不可能延伸到一个答案结点，则一个答案结点，则Bi(x1,x2,xi)取假值，否则取假值，否则取真值。取真值。 于是解向量于是解向量X(1:n)中的第中的第i个分量，就是那些个分量，就是那些选自集合选自集合T (x1,x2,xi-1)且使且使Bi为真的为真的xiAl

10、gorithmHHIT算法8.4：可以放置一个新皇后吗？Procedure PLACE(k)/如果一个皇后能放在第如果一个皇后能放在第k行和行和X(k)列，则返回列，则返回true，否则返回，否则返回false。X是一个全程数组，进入此过程时已置入了是一个全程数组，进入此过程时已置入了k个值。个值。ABS(r)过程返回过程返回r的绝对值的绝对值/global X(1:k); integer i,k;i1while i0 do / 对所有的行，执行以下语句对所有的行，执行以下语句 /X(k)X(k)+1 /移到下一列移到下一列/while X(k)=n and Not PLACE(k) do /此处能放这个皇后吗此处能放这个皇后吗/X(k)X(k)+1 /不能放则转到下一列不能放则转到下一列/repeatif X(k)=n then /找到一个位置找到一个位置/ if k=n then