【問題】 n皇后問題
問題描述：求出在一個(gè)n×n的棋盤上，放置n個(gè)不能互相捕捉的國際象棋“皇后”的所有布局。
這是來源于國際象棋的一個(gè)問題?；屎罂梢匝刂v橫和兩條斜線4個(gè)方向相互捕捉。如圖所示，一個(gè)皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個(gè)皇后相互捕捉。
1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × q × × × × ×
× × ×
× × ×
× ×
× ×
從圖中可以得到以下啟示：一個(gè)合適的解應(yīng)是在每列、每行上只有一個(gè)皇后，且一條斜線上也只有一個(gè)皇后。
求解過程從空配置開始。在第1列至第m列為合理配置的基礎(chǔ)上，再配置第m+1列，直至第n列配置也是合理時(shí)，就找到了一個(gè)解。接著改變第n列配置，希望獲得下一個(gè)解。另外，在任一列上，可能有n種配置。開始時(shí)配置在第1行，以后改變時(shí)，順次選擇第2行、第3行、…、直到第n行。當(dāng)?shù)趎行配置也找不到一個(gè)合理的配置時(shí)，就要回溯，去改變前一列的配置。得到求解皇后問題的算法如下：
{ 輸入棋盤大小值n；
m=0;
good=1;
do {
if (good)
if (m==n)
{ 輸出解；
改變之，形成下一個(gè)候選解;
}
else 擴(kuò)展當(dāng)前候選接至下一列；
else 改變之，形成下一個(gè)候選解；
good=檢查當(dāng)前候選解的合理性；
} while (m!=0);
}
在編寫程序之前，先確定邊式棋盤的數(shù)據(jù)結(jié)構(gòu)。比較直觀的方法是采用一個(gè)二維數(shù)組，但仔細(xì)觀察就會(huì)發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性帶來困難。更好的方法乃是盡可能直接表示那些常用的信息。對(duì)于本題來說，“常用信息”并不是皇后的具體位置，而是“一個(gè)皇后是否已經(jīng)在某行和某條斜線合理地安置好了”。因在某一列上恰好放一個(gè)皇后，引入一個(gè)一維數(shù)組（col[ ]），值col[i]表示在棋盤第i列、col[i]行有一個(gè)皇后。例如：col [3]=4，就表示在棋盤的第3列、第4行上有一個(gè)皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設(shè)定col[0]的初值為0當(dāng)回溯到第0列時(shí)，說明程序已求得全部解，結(jié)束程序運(yùn)行。
為使程序在檢查皇后配置的合理性方面簡(jiǎn)易方便，引入以下三個(gè)工作數(shù)組：
（1） 數(shù)組a[ ]，a[k]表示第k行上還沒有皇后；
（2） 數(shù)組b[ ]，b[k]表示第k列右高左低斜線上沒有皇后；
（3） 數(shù)組 c[ ]，c[k]表示第k列左高右低斜線上沒有皇后；
棋盤中同一右高左低斜線上的方格，他們的行號(hào)與列號(hào)之和相同；同一左高右低斜線上的方格，他們的行號(hào)與列號(hào)之差均相同。
初始時(shí)，所有行和斜線上均沒有皇后，從第1列的第1行配置第一個(gè)皇后開始，在第m列col[m]行放置了一個(gè)合理的皇后后，準(zhǔn)備考察第m+1列時(shí)，在數(shù)組a[ ]、b[ ]和c[ ]中為第m列，col[m]行的位置設(shè)定有皇后標(biāo)志；當(dāng)從第m列回溯到第m-1列，并準(zhǔn)備調(diào)整第m-1列的皇后配置時(shí)，清除在數(shù)組a[ ]、b[ ]和c[ ]中設(shè)置的關(guān)于第m-1列，col[m-1]行有皇后的標(biāo)志。一個(gè)皇后在m列，col[m]行方格內(nèi)配置是合理的，由數(shù)組a[ ]、b[ ]和c[ ]對(duì)應(yīng)位置的值都為1來確定。細(xì)節(jié)見以下程序：
【程序】
# include
# include
# define maxn 20
int n,m,good;
int col[maxn+1],a[maxn+1],b[2*maxn+1],c[2*maxn+1];
void main()
{ int j;
char awn;
printf(“enter n: “); scanf(“%d”,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
m=1; col[1]=1; good=1; col[0]=0;
do {
if (good)
if (m==n)
{ printf(“列\(zhòng)t行”);
for (j=1;j<=n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“enter a character (q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn==’q’||awn==’q’) exit(0);
while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else
{ a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else
{ while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
} while (m!=0);
}
問題描述：求出在一個(gè)n×n的棋盤上，放置n個(gè)不能互相捕捉的國際象棋“皇后”的所有布局。
這是來源于國際象棋的一個(gè)問題?；屎罂梢匝刂v橫和兩條斜線4個(gè)方向相互捕捉。如圖所示，一個(gè)皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個(gè)皇后相互捕捉。
1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × q × × × × ×
× × ×
× × ×
× ×
× ×
從圖中可以得到以下啟示：一個(gè)合適的解應(yīng)是在每列、每行上只有一個(gè)皇后，且一條斜線上也只有一個(gè)皇后。
求解過程從空配置開始。在第1列至第m列為合理配置的基礎(chǔ)上，再配置第m+1列，直至第n列配置也是合理時(shí)，就找到了一個(gè)解。接著改變第n列配置，希望獲得下一個(gè)解。另外，在任一列上，可能有n種配置。開始時(shí)配置在第1行，以后改變時(shí)，順次選擇第2行、第3行、…、直到第n行。當(dāng)?shù)趎行配置也找不到一個(gè)合理的配置時(shí)，就要回溯，去改變前一列的配置。得到求解皇后問題的算法如下：
{ 輸入棋盤大小值n；
m=0;
good=1;
do {
if (good)
if (m==n)
{ 輸出解；
改變之，形成下一個(gè)候選解;
}
else 擴(kuò)展當(dāng)前候選接至下一列；
else 改變之，形成下一個(gè)候選解；
good=檢查當(dāng)前候選解的合理性；
} while (m!=0);
}
在編寫程序之前，先確定邊式棋盤的數(shù)據(jù)結(jié)構(gòu)。比較直觀的方法是采用一個(gè)二維數(shù)組，但仔細(xì)觀察就會(huì)發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性帶來困難。更好的方法乃是盡可能直接表示那些常用的信息。對(duì)于本題來說，“常用信息”并不是皇后的具體位置，而是“一個(gè)皇后是否已經(jīng)在某行和某條斜線合理地安置好了”。因在某一列上恰好放一個(gè)皇后，引入一個(gè)一維數(shù)組（col[ ]），值col[i]表示在棋盤第i列、col[i]行有一個(gè)皇后。例如：col [3]=4，就表示在棋盤的第3列、第4行上有一個(gè)皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設(shè)定col[0]的初值為0當(dāng)回溯到第0列時(shí)，說明程序已求得全部解，結(jié)束程序運(yùn)行。
為使程序在檢查皇后配置的合理性方面簡(jiǎn)易方便，引入以下三個(gè)工作數(shù)組：
（1） 數(shù)組a[ ]，a[k]表示第k行上還沒有皇后；
（2） 數(shù)組b[ ]，b[k]表示第k列右高左低斜線上沒有皇后；
（3） 數(shù)組 c[ ]，c[k]表示第k列左高右低斜線上沒有皇后；
棋盤中同一右高左低斜線上的方格，他們的行號(hào)與列號(hào)之和相同；同一左高右低斜線上的方格，他們的行號(hào)與列號(hào)之差均相同。
初始時(shí)，所有行和斜線上均沒有皇后，從第1列的第1行配置第一個(gè)皇后開始，在第m列col[m]行放置了一個(gè)合理的皇后后，準(zhǔn)備考察第m+1列時(shí)，在數(shù)組a[ ]、b[ ]和c[ ]中為第m列，col[m]行的位置設(shè)定有皇后標(biāo)志；當(dāng)從第m列回溯到第m-1列，并準(zhǔn)備調(diào)整第m-1列的皇后配置時(shí)，清除在數(shù)組a[ ]、b[ ]和c[ ]中設(shè)置的關(guān)于第m-1列，col[m-1]行有皇后的標(biāo)志。一個(gè)皇后在m列，col[m]行方格內(nèi)配置是合理的，由數(shù)組a[ ]、b[ ]和c[ ]對(duì)應(yīng)位置的值都為1來確定。細(xì)節(jié)見以下程序：
【程序】
# include
# include
# define maxn 20
int n,m,good;
int col[maxn+1],a[maxn+1],b[2*maxn+1],c[2*maxn+1];
void main()
{ int j;
char awn;
printf(“enter n: “); scanf(“%d”,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
m=1; col[1]=1; good=1; col[0]=0;
do {
if (good)
if (m==n)
{ printf(“列\(zhòng)t行”);
for (j=1;j<=n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“enter a character (q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn==’q’||awn==’q’) exit(0);
while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else
{ a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else
{ while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
} while (m!=0);
}