DFS-回溯与剪枝-C - N皇后问题

C - N皇后问题

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。Output共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。Sample Input
1

8

5

0
Sample Output
1

92

10

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 int queen[], q[]={}, N, sum=; 

 int check(int n) {

     for(int i=; i<n; i++)

         if(queen[i]==queen[n] || abs(queen[i]-queen[n])==abs(n-i))

             return ;

     return ;

 }

 void DFS(int n) {

     for(int i=; i<N; i++){

         queen[n] = i;

         if(check(n)){

             if(n == N-)

                 sum++;

             else

                 DFS(n+);

         }

     }

 }

 int main(){

     while(scanf("%d",&N)!=EOF){

         if(N==)    break;

         if(q[N]!=)

             printf("%d\n",q[N]);

         else{

             DFS();

             q[N] = sum;

             printf("%d\n",sum);

             sum = ;

         }

     }

     return ;

 }

（1）打表。在main()中提前算出来从1到10的所有N皇后问题的答案，并存储在数组中，等读取输入后立刻输出。如果不打表，而是输入N后再单独计算输出，会超时。

（2）递归搜索DFS()。递归程序十分简洁，把第一个皇后按行放到棋盘上，然后递归放置其他的皇后，直到放完。

（3）回溯判断check()。判断新放置的皇后和已经放好的皇后在横向、纵向、斜对角方向是否冲突。其中，横向并不需要判断，因为在递归的时候已经是按不同行放置的。

（4）模块化编程。例如check()的内容很少，其实可以直接写在DFS()内部，不用单独写成一个函数。但是单独写成函数，把功能模块化，好处很多，例如逻辑清晰，容易差错等。建议在写程序的时候尽量把能分开的功能单独写成函数，这样可以大大减少编码和调试的时间。

巴特西

DFS-回溯与剪枝-C - N皇后问题

最新文章

热门文章