8皇后算法.cpp

皇后算法111 很经典的 内含两种 希望大家喜欢

/*
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；
 数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；
 数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为0；

*/
#include "stdio.h"

/*本文档版权归楼竞网站所有，转载请注明出处。*/

static char Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int iQueenNum=0;  /*记录总的棋盘状态数*/

void qu(int i);  /*参数i代表行*/

int main()
{
 int il,ic;

 /*棋盘初始化，空格为*，放置皇后的地方为@  */
 for(il=0;il<8;il++)
 {
  a[il]=0;  /*列标记初始化，表示无列冲突*/
  for(ic=0;ic<8;ic++)
   Queen[il][ic]='*';
 }

 /*主、从对角线标记初始化，表示没有冲突*/
 for(il=0;il<15;il++)
  b[il]=c[il]=0;

 qu(0);
 return 0;
}

void qu(int i)
{
 int ic;

 for(ic=0;ic<8;ic++)
      {
       if(a[ic]==0&&b[i-ic+7]==0&&c[i+ic]==0) /*如果无冲突*/
               {
             Queen[i][ic]='@'; /*放皇后*/
              a[ic]=1;   /*标记，下一次该列上不能放皇后*/
              b[i-ic+7]=1;  /*标记，下一次该主对角线上不能放皇后*/
              c[i+ic]=1;   /*标记，下一次该从对角线上不能放皇后*/
              if(i<7) qu(i+1);  /*如果行还没有遍历完，进入下一行*/
                      else     /*否则输出*/
                        {
                       /*输出棋盘状态www.LouJing.com*/
                          int il,ic;
                          printf("第%d种状态为：\n",++iQueenNum);
                              for(il=0;il<8;il++)
                                             {
                                               for(ic=0;ic<8;ic++)
                                                printf("%c  ",Queen[il][ic]);
                                                printf("\n");
                                                             }
                                printf("\n\n");
                         }
   
                     /*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/
                   Queen[i][ic]='*';
                   a[ic]=0;
                   b[i-ic+7]=0;
                   c[i+ic]=0;
                 }
        }
}



















1.问题描述：在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。

2.设计思想与分析：
    基本思路：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。 


#include <iostream.h>
#include <math.h>

/*检查可不可以放置一个新的皇后*/
bool place(int k, int *X)
{
 int i;
 i=1;
 while(i<k)
 {
  if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))
   return false;
  i++;
 }
 return true;
}
/*求解问题的所有解*/
void Nqueens(int n,int *X)
{
 int k;
 
 X[1]=0;k=1;
 while(k>0)
 {
  X[k]=X[k]+1;
 
  while((X[k]<=n)&&(!place(k, X)))
    X[k]=X[k]+1;
 
  if(X[k]<=n)
   if(k==n)
   {
    for(int i=1;i<=n;i++)
    cout<<X[i]<<" ";
    cout<<"\n";
   }
   else
   {
    k=k+1;
    X[k]=0;
   }
   
  else k=k-1;
 }
 
}

void main()
{
 cout<<"|--------------N皇后问题--------------|"<<endl;
 cout<<"|---power by zhanjiantao(028054115)---|"<<endl;
 cout<<"|-------------------------------------|"<<endl<<endl;
 int n;
 int *X;
 int i;
  while(i)
  {
   cout<<"请输入皇后的个数:";
   cin>>n;
   X=new int[n];
   cout<<"问题的解有:"<<endl;
   Nqueens(n,X);
   cout<<"Press<1> to run again"<<endl;
   cout<<"Press<0> to exit"<<endl;
   cin>>i;
  }
 
}