八皇後問題是十九世紀著名的數學家高斯於1850年提出的。問題是:在8×8的棋盤上擺放八個皇後,使其不能互相攻擊,即任意兩個皇後都不能處於同一行、同一列或同一斜線上。可以把八皇後問題擴展到n皇後問題,即在n×n的棋盤上擺放n個皇後,使任意兩個皇後都不能處於同一行、同一列或同一斜線上。例如,八皇後問題的一個解為:
顯然,棋盤的每一行上可以而且必須擺放一個皇後,所以,n皇後問題的可能解用一個n元向量X=(x1,x2, …,xn)表示,其中,1≤i≤n並且1≤xi≤n,即第i個皇後放在第i行第xi列上。 由於兩個皇後不能位於同一列上,所以,解向量X必須滿足約束條件: xi≠xj (式1) 若兩個皇後擺放的位置分別是(i, xi)和(j, xj),在棋盤上斜率為-1的斜線上,滿足條件i-j= xi-xj,在棋盤上斜率為1的斜線上,滿足條件i+j= xi+xj,綜合兩種情況,由於兩個皇後不能位於同一斜線上,所以,解向量X必須滿足約束條件: |i-xi|≠|j-xj| (式2) 為了簡化問題,下面討論四皇後問題。 四皇後問題的解空間樹是一個完全4叉樹,樹的根結點表示搜索的初始狀態,從根結點到第2層結點對應皇後1在棋盤中第1行的可能擺放位置,從第2層結點 到第3層結點對應皇後2在棋盤中第2行的可能擺放位置,依此類推。 回溯法求解4皇後問題的搜索過程 下面附上八皇後問題的C代碼,八皇後問題一共有92種方案#include <stdio.h>
#include <math.h>
#define N_QUEENS 8
void Queen();
int Place(int * x, int k);
int solutions = 0; //總的解決方案數目
int main(void)
{
Queen();
printf("Total %d solutions\n", solutions);
return 0;
}
void Queen()
{
int i, k;
int x[N_QUEENS+1]; //為了表述方便,我們不使用x[0],因此數組大小多加1
k = 1;
for (i = 1; i <= N_QUEENS; i++)//初始化
x[i] = 0;
while (k >= 1)
{
x[k]++;//在下一列放置第k個皇後
while (x[k] <= N_QUEENS && !Place(x, k))
x[k]++;//只要有沖突,就搜索下一列,試圖找到第一個不沖突的
if (x[k] > N_QUEENS)//這說明第k行所有的都沖突,重置x[k],回溯,這兩行代碼才是關鍵
{
x[k] = 0;
k--;
}
else if(k < N_QUEENS)//放置下一個皇後
{
k++;
}
else // 得到一個解,輸出
{
for (i = 1; i <= N_QUEENS; i++)
printf("%d, ", x[i]);
printf("\n");
solutions++;
// return; //如果只想得到一個解,而不是所有的解,那麼需要return 語句
}
}
}
int Place(int * x, int k)//考察皇後k放置在x[k]列是否發生沖突,發生沖突返回0,否則返回1
{
int i;
for (i = 1; i < k; i++)
if (x[k] == x[i] || abs(k-i) == abs(x[k]-x[i]))
return 0;
return 1;
}
參考 資料 :北京科技大學 羅熊 《算法設計與分析》課件 第6章 回溯法