“八皇后”問題遞歸法求解

*
八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯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種狀態為：
* * * @ * * * * 
* * * * * * @ *