- 相關(guān)推薦
程序員面試?yán)}
面試?yán)}：八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是 19 世紀(jì)著名的數(shù)學(xué)家高斯 1850 年提出：在 8×8 格的國際象棋盤上擺放 8 個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。[英國某著名計(jì)算機(jī)圖形圖像公司面試題]
解析：遞歸實(shí)現(xiàn) n 皇后問題。
算法分析：
數(shù)組 a、b、c 分別用來標(biāo)記沖突，a 數(shù)組代表列沖突，從 a[0]~a[7]代表第 0 列到第 7 列。如果某列上已經(jīng)有皇后，則為 1，否則為 0。
數(shù)組 b 代表主對(duì)角線沖突，為 b[i-j+7]，即從 b[0]~b[14]。如果某條主對(duì)角線上已經(jīng)有皇后，則為 1，否則為 0。
數(shù)組 c 代表從對(duì)角線沖突，為 c[i+j]，即從 c[0]~c[14]。如果某條從對(duì)角線上已經(jīng)有皇后，則為 1，否則為 0。
代碼如下：
#include
static char Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int iQueenNum=0; //記錄總的棋盤狀態(tài)數(shù)
void qu(int i);
//參數(shù)i 代表行
int main()
{
int iLine,iColumn;
//棋盤初始化，空格為*，放置皇后的地方為@
for(iLine=0;iLine<8;iLine++)
{
a[iLine]=0; //列標(biāo)記初始化，表示無列沖突
for(iColumn=0;iColumn<8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、從對(duì)角線標(biāo)記初始化，表示沒有沖突
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;
//標(biāo)記，下一次該列上不能放皇后
b[i-iColumn+7]=1;
//標(biāo)記，下一次該主對(duì)角線上不能放皇后
c[i+iColumn]=1;
//標(biāo)記，下一次該從對(duì)角線上不能放皇后
if(i<7) qu(i+1);
//如果行還沒有遍歷完，進(jìn)入下一行
else //否則輸出
{
//輸出棋盤狀態(tài)
int iLine,iColumn;
printf("第%d 種狀態(tài)為： ",++iQueenNum);
for(iLine=0;iLine<8;iLine++)
{
for(iColumn=0;iColumn<8;iColumn++)
printf("%c ",Queen[iLine][iColumn]);
printf(" ");
}
printf(" ");
}
//如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯，重置
Queen[i][iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}
【程序員面試?yán)}】相關(guān)文章：
筆試題例題06-21
程序員面試技巧07-13
程序員面試經(jīng)驗(yàn)07-13
程序員面試寶典07-09
高考典型例題分析06-24
程序員面試項(xiàng)目經(jīng)驗(yàn)06-30
程序員面試技巧總結(jié)07-13
程序員筆試面試寶典07-13
程序員面試題精選07-12