用回溯法求解八皇後問題

八皇後問題是十九世紀著名的數學家高斯於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章 回溯法