文档介绍：用回溯法求解 n皇后问题学号: 1202121463 姓名:程园 1 回溯法的基本思想回溯法的基本思想是在问题的解空间树上按深度优先搜索策略,从根节点出发搜索整个解空间。搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索, 逐层向其祖先节点回溯。否则, 进入该子树。 2 n皇后问题描述在nxn的棋盘上放置彼此不受攻击的 n 个皇后。任何 2个皇后不能放在同一行、同一列、同一对角线上。 3 分析问题 , 第一行有 n个位置可以放,我们用 x[1] 来表示第一行的皇后所在的列,第二行有 n-1 个位置可以放,我们用 x[2] 来表示第二行皇后所在的列······ 因此,我们用一个数组 x[n] 来表示问题的解, x[i] 表示皇后 i放在第 i行第 x[i] 列。 x[i] ≠ x[j] ,i≠ j ?分析问题问题分析 4 分析问题如何保证任何两个皇后不再一条斜线上?设两个皇后 q1 和 q2 放在( i,j)和( k,l)位置上,如果 q1 和 q2 在斜率为-1的对角线上, 那么 i - j = k - l 成立,如果在斜率为1的对角线上,那么 i + j = k + l 成立,由此可知只要 | i - k | ≠ | j - l | 成立, q1 和 q2 就不再同一条斜线上。 | i - k | ≠ | j - l | ?问题分析 5 分析问题 n叉树表示解空间,现在以 n=4 为例: 问题分析 1× ×× ××× √√× 6 分析问题//求解的递归函数 void Queen(int i,int n) { if(i>n) Output(); else { for(int j=1;j<=n;++j) // j 代表列值 { int k=1; x[i