“八皇后”问题递归法求解.txt

“八皇后”问题递归法求解 * 八皇后问题是一个古老而著名的问题

“八皇后”问题递归法求解

*
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯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 iLine,iColumn;

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

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

qu(0);
return 0;
}

void qu(int i)
{
int iColumn;

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


共计92种结果如下：

第1种状态为：
@ * * * * * * * 
* * * * @ * * * 
* * * * * * * @ 
* * * * * @ * * 
* * @ * * * * * 
* * * * * * @ * 
* @ * * * * * * 
* * * @ * * * * 


第2种状态为：
@ * * * * * * * 
* * * * * @ * * 
* * * * * * * @ 
* * @ * * * * * 
* * * * * * @ * 
* * * @ * * * * 
* @ * * * * * * 
* * * * @ * * * 


第3种状态为：
@ * * * * * * * 
* * * * * * @ * 
* * * @ * * * * 
* * * * * @ * * 
* * * * * * * @ 
* @ * * * * * * 
* * * * @ * * * 
* * @ * * * * * 


第4种状态为：
@ * * * * * * * 
* * * * * * @ * 
* * * * @ * * * 
* * * * * * * @ 
* @ * * * * * * 
* * * @ * * * * 
* * * * * @ * * 
* * @ * * * * * 


第5种状态为：
* @ * * * * * * 
* * * @ * * * * 
* * * * * @ * * 
* * * * * * * @ 
* * @ * * * * * 
@ * * * * * * * 
* * * * * * @ * 
* * * * @ * * * 


第6种状态为：
* @ * * * * * * 
* * * * @ * * * 
* * * * * * @ * 
@ * * * * * * * 
* * @ * * * * * 
* * * * * * * @ 
* * * * * @ * * 
* * * @ * * * * 


第7种状态为：
* @ * * * * * * 
* * * * @ * * * 
* * * * * * @ * 
* * * @ * * * * 
@ * * * * * * * 
* * * * * * * @ 
* * * * * @ * * 
* * @ * * * * * 


第8种状态为：
* @ * * * * * * 
* * * * * @ * * 
@ * * * * * * * 
* * * * * * @ * 
* * * @ * * * * 
* * * * * * * @ 
* * @ * * * * * 
* * * * @ * * * 


第9种状态为：
* @ * * * * * * 
* * * * * @ * * 
* * * * * * * @ 
* * @ * * * * * 
@ * * * * * * * 
* * * @ * * * * 
* * * * * * @ * 
* * * * @ * * * 


第10种状态为：
* @ * * * * * * 
* * * * * * @ * 
* * @ * * * * * 
* * * * * @ * * 
* * * * * * * @ 
* * * * @ * * * 
@ * * * * * * * 
* * * @ * * * * 


第11种状态为：
* @ * * * * * * 
* * * * * * @ * 
* * * * @ * * * 
* * * * * * * @ 
@ * * * * * * * 
* * * @ * * * * 
* * * * * @ * * 
* * @ * * * * * 


第12种状态为：
* @ * * * * * * 
* * * * * * * @ 
* * * * * @ * * 
@ * * * * * * * 
* * @ * * * * * 
* * * * @ * * * 
* * * * * * @ * 
* * * @ * * * * 


第13种状态为：
* * @ * * * * * 
@ * * * * * * * 
* * * * * * @ * 
* * * * @ * * * 
* * * * * * * @ 
* @ * * * * * * 
* * * @ * * * * 
* * * * * @ * * 


第14种状态为：
* * @ * * * * * 
* * * * @ * * * 
* @ * * * * * * 
* * * * * * * @ 
@ * * * * * * * 
* * * * * * @ * 
* * * @ * * * * 
* * * * * @ * * 


第15种状态为：
* * @ * * * * * 
* * * * @ * * * 
* @ * * * * * * 
* * * * * * * @ 
* * * * * @ * * 
* * * @ * * * * 
* * * * * * @ * 
@ * * * * * * * 


第16种状态为：
* * @ * * * * * 
* * * * @ * * * 
* * * * * * @ * 
@ * * * * * * * 
* * * @ * * * * 
* @ * * * * * * 
* * * * * * * @ 
* * * * * @ * * 


第17种状态为：
* * @ * * * * * 
* * * * @ * * * 
* * * * * * * @ 
* * * @ * * * * 
@ * * * * * * * 
* * * * * * @ * 
* @ * * * * * * 
* * * * * @ * * 


第18种状态为：
* * @ * * * * * 
* * * * * @ * * 
* @ * * * * * * 
* * * * @ * * * 
* * * * * * * @ 
@ * * * * * * * 
* * * * * * @ * 
* * * @ * * * * 


第19种状态为：
* * @ * * * * * 
* * * * * @ * * 
* @ * * * * * * 
* * * * * * @ * 
@ * * * * * * * 
* * * @ * * * * 
* * * * * * * @ 
* * * * @ * * * 


第20种状态为：
* * @ * * * * * 
* * * * * @ * * 
* @ * * * * * * 
* * * * * * @ * 
* * * * @ * * * 
@ * * * * * * * 
* * * * * * * @ 
* * * @ * * * * 


第21种状态为：
* * @ * * * * * 
* * * * * @ * * 
* * * @ * * * * 
@ * * * * * * * 
* * * * * * * @ 
* * * * @ * * * 
* * * * * * @ * 
* @ * * * * * * 


第22种状态为：
* * @ * * * * * 
* * * * * @ * * 
* * * @ * * * * 
* @ * * * * * * 
* * * * * * * @ 
* * * * @ * * * 
* * * * * * @ * 
@ * * * * * * * 


第23种状态为：
* * @ * * * * * 
* * * * * @ * * 
* * * * * * * @ 
@ * * * * * * * 
* * * @ * * * * 
* * * * * * @ * 
* * * * @ * * * 
* @ * * * * * * 


第24种状态为：
* * @ * * * * * 
* * * * * @ * * 
* * * * * * * @ 
@ * * * * * * * 
* * * * @ * * * 
* * * * * * @ * 
* @ * * * * * * 
* * * @ * * * * 


第25种状态为：
* * @ * * * * * 
* * * * * @ * * 
* * * * * * * @ 
* @ * * * * * * 
* * * @ * * * * 
@ * * * * * * * 
* * * * * * @ * 
* * * * @ * * * 


第26种状态为：
* * @ * * * * * 
* * * * * * @ * 
* @ * * * * * * 
* * * * * * * @ 
* * * * @ * * * 
@ * * * * * * * 
* * * @ * * * * 
* * * * * @ * * 


第27种状态为：
* * @ * * * * * 
* * * * * * @ * 
* @ * * * * * * 
* * * * * * * @ 
* * * * * @ * * 
* * * @ * * * * 
@ * * * * * * * 
* * * * @ * * * 


第28种状态为：
* * @ * * * * * 
* * * * * * * @ 
* * * @ * * * * 
* * * * * * @ * 
@ * * * * * * * 
* * * * * @ * * 
* @ * * * * * * 
* * * * @ * * * 


第29种状态为：
* * * @ * * * * 
@ * * * * * * * 
* * * * @ * * * 
* * * * * * * @ 
* @ * * * * * * 
* * * * * * @ * 
* * @ * * * * * 
* * * * * @ * * 


第30种状态为：
* * * @ * * * * 
@ * * * * * * * 
* * * * @ * * * 
* * * * * * * @ 
* * * * * @ * * 
* * @ * * * * * 
* * * * * * @ * 
* @ * * * * * * 


第31种状态为：
* * * @ * * * * 
* @ * * * * * * 
* * * * @ * * * 
* * * * * * * @ 
* * * * * @ * * 
@ * * * * * * * 
* * @ * * * * * 
* * * * * * @ * 


第32种状态为：
* * * @ * * * * 
* @ * * * * * * 
* * * * * * @ * 
* * @ * * * * * 
* * * * * @ * * 
* * * * * * * @ 
@ * * * * * * * 
* * * * @ * * * 


第33种状态为：
* * * @ * * * * 
* @ * * * * * * 
* * * * * * @ * 
* * @ * * * * * 
* * * * * @ * * 
* * * * * * * @ 
* * * * @ * * * 
@ * * * * * * * 


第34种状态为：
* * * @ * * * * 
* @ * * * * * * 
* * * * * * @ * 
* * * * @ * * * 
@ * * * * * * * 
* * * * * * * @ 
* * * * * @ * * 
* * @ * * * * * 


第35种状态为：
* * * @ * * * * 
* @ * * * * * * 
* * * * * * * @ 
* * * * @ * * * 
* * * * * * @ * 
@ * * * * * * * 
* * @ * * * * * 
* * * * * @ * * 


第36种状态为：
* * * @ * * * * 
* @ * * * * * * 
* * * * * * * @ 
* * * * * @ * * 
@ * * * * * * * 
* * @ * * * * * 
* * * * @ * * * 
* * * * * * @ * 


第37种状态为：
* * * @ * * * * 
* * * * * @ * * 
@ * * * * * * * 
* * * * @ * * * 
* @ * * * * * * 
* * * * * * * @ 
* * @ * * * * * 
* * * * * * @ * 


第38种状态为：
* * * @ * * * * 
* * * * * @ * * 
* * * * * * * @ 
* @ * * * * * * 
* * * * * * @ * 
@ * * * * * * * 
* * @ * * * * * 
* * * * @ * * * 


第39种状态为：
* * * @ * * * * 
* * * * * @ * * 
* * * * * * * @ 
* * @ * * * * * 
@ * * * * * * * 
* * * * * * @ * 
* * * * @ * * * 
* @ * * * * * * 


第40种状态为：
* * * @ * * * * 
* * * * * * @ * 
@ * * * * * * * 
* * * * * * * @ 
* * * * @ * * * 
* @ * * * * * * 
* * * * * @ * * 
* * @ * * * * * 


第41种状态为：
* * * @ * * * * 
* * * * * * @ * 
* * @ * * * * * 
* * * * * * * @ 
* @ * * * * * * 
* * * * @ * * * 
@ * * * * * * * 
* * * * * @ * * 


第42种状态为：
* * * @ * * * * 
* * * * * * @ * 
* * * * @ * * * 
* @ * * * * * * 
* * * * * @ * * 
@ * * * * * * * 
* * @ * * * * * 
* * * * * * * @ 


第43种状态为：
* * * @ * * * * 
* * * * * * @ *