首页 > 代码库 > 华为机试—N皇后问题(高级题160分:两种回溯法解决 吐血整理)
华为机试—N皇后问题(高级题160分:两种回溯法解决 吐血整理)
一、问题描述:
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上。
输入:
给定棋盘的大小n (n ≤ 13)
输出:
输出有多少种放置方法。
二、解题思路:
要解决N皇后问题,其实就是要解决好怎么放置这n个皇后,每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线,在这里我们可以以行优先,就是说皇后的行号按顺序递增,只考虑第i个皇后放置在第i行的哪一列,所以在放置第i个皇后的时候,可以从第1列判断起,如果可以放置在第1个位置,则跳到下一行放置下一个皇后。如果不能,则跳到下一列...直到最后一列,如果最后一列也不能放置,则说明此时放置方法出错,则回到上一个皇后向之前放置的下一列重新放置。此即是回溯法的精髓所在。当第n个皇后放置成功后,即得到一个可行解,此时再回到上一个皇后重新放置寻找下一个可行解...如此后,即可找出一个n皇后问题的所有可行解。
三、复杂度分析:
关于N皇后问题的复杂度问题可以说是众说纷纭了,自己也改变过好几次,刚开始以为棋盘是n行n列,所以理所当然应该是n^2,后来发现在每列选择可否放置的比较上又做了一次循环,所以应该是n^3,但想了很久,发现判断可否放置的时候不是每次都循环到n,它是根据皇后i的取值而变化的,所以复杂度应该是1/3 n^3左右,即是小于n^3的。
四、测试代码:
两个实现方法,一个是递归回溯,一个是迭代回溯,思路都一样,只是形式不同罢了。
递归回溯
#include <stdio.h> #include <math.h> #define N 15 int n; //皇后个数 int sum = 0; //可行解个数 int x[N]; //皇后放置的列数 /* *判断函数,判断第k个皇后是否可以放在某一个位置 *如果与之前的皇后出现在同一列或同一对角线则放置失败,返回0,否则返回1 */ int place(int k) { int i; for(i=1;i<k;i++) if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i]) return 0; return 1; } /* *求解可行解函数,当第t个皇后可以放置在t行的某一位置时,继续放置下一皇后,直到 *所有皇后放置结束,如果某一皇后不能放置,则移向下一列放置,如果这一列都不能放 *置或所有皇后放置结束,返回上一皇后重新放置,最终返回所有可行解个数。 */ int queen(int t) { if(t>n) //当放置的皇后超过n时,可行解个数加1 sum++; else for(int i=1;i<=n;i++) { x[t] = i; //标明第t个皇后放在第i列 if(place(t)) //如果可以放在某一位置,则继续放下一皇后 queen(t+1); } return sum; } int main() { int t; while(~scanf("%d",&n)){ t = queen(1); if(n == 0) //如果n=0,则可行解个数为0,这种情况一定不要忽略 t = 0; printf("%d\n",t); sum=0; } return 0; }
迭代回溯
#include <stdio.h> #include <math.h> #define N 15 int n; int sum = 0; int x[N]; int place(int k) { int i; for(i=1;i<k;i++) if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i]) return 0; return 1; } int queen() { x[1] = 0; int t=1; while(t>0) { x[t]+=1; while(x[t]<=n && !place(t)) x[t]++; if(x[t]<=n) if(t == n) { for(int k=1;k<=n;k++) printf("%d ",x[k]); printf("\n"); sum++; } else x[++t] = 0; else t--; } return sum; } int main() { int t; while(scanf("%d",&n)){ t = queen(); printf("%d\n",t); sum=0; } return 0; }
五、测试结果:
六、总结
迭代回溯的注释因为和递归回溯差不多,所以就不再附注了。在这里我们可以看到,递归回溯非常简单,结构很清晰,但它有一个潜在的问题存在,即当随着变量n的增大,递归法的复杂度也将成几何级增长,也有可能会出现重复的情况,所以我们在解决问题时,如果能用迭代法解决,最好还是不要用递归法,除非你已经对这个递归了如指掌了。
通过这个N皇后问题,我想大概已经把回溯法讲得很清楚了吧,回溯法得到的解展开就是一个树,很多方法都是可以通过回溯法来解决的,效率很高,但如果基数过大的话,回溯法就显得不是那么适用了,这也是回溯法的弱势吧。比如说这个N皇后问题,好像当n>60的时候,回溯法就不能完全地解决问题了,这时可以考虑用概率算法来解决,它可以解决很大的基数,只不过结果不是很精确而已。所以我们在面对一个问题时,具体是使用什么算法还是要结合实际情况来考虑的,目的都是更方便、更准确地解决问题。
华为机试—N皇后问题(高级题160分:两种回溯法解决 吐血整理)