程序員遞歸面試問題及解析

面試例題 2：八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是 19 世紀著名的數學家高斯 1850 年提出：在 88 格的國際象棋盤上擺放 8 個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。[英國某著名計算機圖形圖像公司面試題]
解析：遞歸實現 n 皇后問題。
算法分析：
數組 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[i][icolumn]='@';
//放皇后
a[icolumn]=1;
//標記，下一次該列上不能放皇后
b[i-icolumn+7]=1;
//標記，下一次該主對角線上不能放皇后
c[i+icolumn]=1;
//標記，下一次該從對角線上不能放皇后
if(i<7) qu(i+1);
//如果行還沒有遍歷完，進入下一行
else //否則輸出
{
//輸出棋盤狀態
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[i][icolumn]='*';
a[icolumn]=0;
b[i-icolumn+7]=0;
c[i+icolumn]=0;
}
}
}