不甘心的皇后 http://acm.scu.edu.cn/soj/problem.action?id=1082 这是我做过印象最深刻的编程作品--皇后问题，我把对它的理解和分析过程整理 在这里了，希望老师过目。我自己也经常关注 ACM，并且希望在之后的学习生活 中能够参加到 ACM 比赛中去锻炼思维，从中获得快乐。 印象最深刻的程序 #include #include #include int how,zero[10]; int main() { # 变量 how 表示放置的皇后种数，zero 数组存放皇后的位置 void count(int* q, int length, int now); while (1) { int n, queen[10]; scanf_s("%d", &n); if (n == 0) { break; # n 表示棋盘大小，queen 是存放皇后的数组，最多十个皇后。 # 输入 n # 如果棋盘边长为 0，则无法放置皇后 # 跳出循环 } memset(zero, -1, sizeof(zero)); # 将 zero 数组中的值都初始化为-1 how = 0; for (int i = 0; i < n; i++) { scanf_s("%d",&queen[i]); if (queen[i] == 0) { # 输入每列已有的皇后位置 # 如果皇后位置为 0，表示这一列还没有皇后 zero[i] = 0; # 那么 zero 数组中对应的列值也为 0 # 从第一列开始计算可放置皇后的方法数 # 输出该棋盘可放置皇后的方法种数 } } count(queen, n, 0); printf("%d\n", how); } return 0; } # 比较两个数大小，输出较大的一个值 int max(int a, int b) { if (a > b) { return a; } else { } return b; 

} # 计算满足要求的情况数量 void count(int *q,int length,int now) { # 函数变量：queen 数组，棋盘大小，当前列值 if (now == length) { # 如果当前位置等于棋盘大小 int var; for (var = 0; var < length-1&&pow(q[var]-q[var+1],2)<=1; var++) { # 从第一列开始遍 # 设置整数变量 历，如果每两个相邻列皇后之间的行距离大于 1，则停止遍历 ; } if (var == length - 1)how++; # 如果停止遍历后的 var 正好等于 length-1，即已经遍 历完所有列，则说明这种放置皇后的方法是正确的，方法数加 1 return; } if (zero[now]==0) { if (now==0) { # 如果当前列没有皇后 # 如果是第一列 for (int j = 1; j <= length; j++) { # 从第一列的每一行开始遍历 q[now] = j; count(q, length, now + 1); # 计算第一列皇后在第 j 行时，棋盘可放 置皇后种数 } } else { # 如果不是第一列，那么该列皇后的位置范围应为[前一 列皇后位置-1，前一列皇后位置+1] for (int j = max(1,q[now-1]-1); j <= length&&j<=q[now-1]+1; j++) { # max(1,q[now-1]-1) 是为了确保皇后位置最小是 1 q[now] = j; count(q, length, now + 1); # 计算当前列皇后在第 j 行时，棋盘可放置皇 后种数 } } } else { } count(q, length, now + 1); # 当前列皇后已确定，计算后续列棋盘可放置皇后种数 } 采用递归调用函数的思想，算法思路如下： 1、 从棋盘的第一列开始，判断当前列的皇后位置是否已经确定。若每一列皇后位置已经确 定，则跳到下一行。若尚未确定，则根据上一列皇后的位置确定该列皇后位置的范围， 然后在此范围内依次遍历，调用 count 函数计算棋盘可放置皇后种数。 注意：第一列比较特殊，需要单独处理。因为当第一列的皇后位置不确定时，它可以在 任意一行。所以单独计算。 

而对于其它列，该列皇后的位置范围应为[前一列皇后位置-1，前一列皇后位置+1]。 另外，为了避免前一列皇后位置-1=0 的情况，这时该列皇后位置是无意义的，所以添 加了一个 max 函数，取“前一列皇后位置-1”的值和 1 的较大值。 2、 当遍历到最后一列时，所有皇后摆放完毕，判断当前摆放的棋盘是否满足题目要求。即 采用 for 循环判断每两个相邻列皇后之间的行距离是否都小于等于 1。如果满足题目要 求，则摆放皇后种数增加 1。函数终止。 理解和总结： 这道题和八皇后问题有些类似。但是条件不同，这道题需要确保棋盘中每两个相邻列的 皇后之间的行距离最多只能差一格。所以只有先确定第一列的皇后位置，才能确定第二列的 皇后位置，继而确定第三列、第四列等等。而每一列的皇后位置又有多种可能，因此想到使 用深度优先搜索算法。对于每一列的可选择皇后位置中，选择一个位置作为出发点，然后依 次从该点出发搜索下一列可能的皇后位置，直至棋盘中所有列都被搜索过为止，然后判断这 条路径是否满足题目要求。 虽然我的编程水平还达不到做此类题目游刃有余，但我很享受沉浸其中思考解决编程思 维问题的过程。