HDOJ--2553_综合

N皇后问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14755 Accepted Submission(s): 6719

Problem Description

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

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

Sample Output

很经典的一类题型：

算法是回溯法+递归，以下是这道题的常规解法：

//N queen problem
// 一维数组表示棋盘
//回溯法+递归
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define NULLL -10000 /*棋盘的初始值*/
int a[100];
using namespace std;
void init(int queen)  //对棋盘进行初始化  
{  int *p;  for (p = a; p < a + queen; ++p)   {  *p = NULLL;  }  
}   
int judge(int row,int col,int queen)  /*用来判断第row行第col列是否可以放置皇后*/
{int i;for(i=0;i<queen;++i){if(a[i]==col||abs(i-row)==abs(a[i]-col))return 0;} return 1;
}
void QUEEN(int queen)
{int i=0,j=0;int sum=0;while(i<queen){while(j<queen)     /*对i行的每一列进行探索，看是否可以放置皇后*/{if(judge(i,j,queen))   /*如果该位置可以放置皇后*/{a[i]=j;j=0;break;   /*第i行放置皇后后，需要继续探索下一行皇后位置，所以将j清零*/ }else++j; }if(a[i]==NULLL)     /*如果第i行没有找到可以放皇后的位置*/{if(i==0)break;   /*回溯到第一行，若仍然无法找到放皇后的位置，所有解已经找到，结束程序*/ else{--i;j=a[i]+1;a[i]=NULLL;continue;}}if(i==queen-1)    /*如果在最后一行找到皇后，则找到一种结果*/ {++sum;j=a[i]+1;a[i]=NULLL;continue;}++i;}cout<<sum<<endl;
}
int main()
{int queen;while(cin>>queen){if(queen==0)break;init(queen);QUEEN(queen);}return 0;}

但是在杭电面前，这种常规写法也被TLE了，于是当初的我一怒之下进行了打表。

以下是我的打表AC代码：

#include<iostream>
using namespace std;
int main()
{int n;while(cin>>n){if(n==0)break;switch(n){case 1:cout<<"1"<<endl;break;case 2:cout<<"0"<<endl;break;case 3:cout<<"0"<<endl;break;case 4:cout<<"2"<<endl;break;case 5:cout<<"10"<<endl;break;case 6:cout<<"4"<<endl;break;case 7:cout<<"40"<<endl;break;case 8:cout<<"92"<<endl;break;case 9:cout<<"352"<<endl;break;case 10:cout<<"724"<<endl;break;}} return 0;}

当然啦，在比赛时碰见我这种情况就直接打表吧~

在这里我还是要给出比常规解法更优化的方法：
dfs+状态压缩：

以下是优化后的解法：

#include<stdio.h>  
int N,SchemeNum;  
void DFS(int Col,int MainDiag,int ContDiag)  
{  if(Col==(1<<N)-1) { ++SchemeNum;  return; }  int emptycol=(((1<<N)-1)&~(Col|MainDiag|ContDiag));  while(emptycol)  {  int curcol=(emptycol)&((~emptycol)+1);  emptycol&=~curcol;  DFS(Col|curcol,(MainDiag|curcol)>>1,(ContDiag|curcol)<<1);  }  
}  
int main()  
{  while(scanf("%d",&N)==1&&N)  {  SchemeNum=0;  DFS(0,0,0);  printf("%d\n",SchemeNum);  }  return 0;  
}