C语言八皇后问题解决方法示例【暴力法与回溯法】

#include<cstdio>#include<cmath>const int maxn=11;int count=0;//P为当前排列,hashTable记录整数x是否已经在P中int n,P[maxn] ,hashTable[maxn] = {false};//当前处理排列的第index号位void generateP(int index){  if(index==n+1)//递归边界,已经处理完排列的1~n位  {  bool flag=true;//flag为true表示当前排列为一个合法方案  for(int i=1;i<=n;i++)  {    for(int j=i+1;j<=n;j++)    {      if(abs(i-j)==abs(P[i]-P[j]))//如果在对角线上      {        flag=false;//不合法      }    }   }   if(flag)  count++;//若当前方案合法,count+1   return ; } for(int x=1 ; x<=n ; x++)//枚举1~n,试图将x填入P[index] {  if(hashTable[x]==false)//如果x不在P[0]~P[index-1]中  {    P[index]=x; //令P的第index位为x,即把x加入当前排列    hashTable[x]=true;//记x已在P中    generateP(index+1);//处理排列的第index+1号位    hashTable[x]=false;//已处理完P[index]为x的子问题,还原状态}}}int main(){  n=8;  generateP(1);  printf("%d/n",count);  return 0;}

#include<cstdio>#include<cmath>const int maxn=11;int count=0;//P为当前排列,hashTable记录整数x是否已经在P中int n,P[maxn] ,hashTable[maxn] = {false};//当前处理排列的第index号位void generateP(int index){  if(index==n+1)  {    count++;    return ;  }  for(int x=1;x<=n;x++)//第x行  {    if(hashTable[x]==false)//第x行还没有皇后    {      bool flag=true;//flag表示当前皇后不会和之前的皇后冲突      for(int pre=1;pre<index;pre++)//遍历之前的皇后      {//第index行的皇后的行号为x,第pre列皇后的行号为P[pre]        if(abs(index-pre)==abs(x-P[pre]))        {          flag=false;//与之前的皇后在一条对角线,冲突          break;         }       }       if(flag)//如果可以把皇后放在第x行       {        P[index]=x;//令第index列皇后的行数为x         hashTable[x]=true;//第x行已经被占用         generateP(index+1);//递归处理第index+1行皇后         hashTable[x]=false;//递归完毕,还原第x行为为占用状态       }     }   }}int main(){  n=8;  generateP(1);  printf("%d/n",count);  return 0;}