回溯——n皇後問題

思想：

用回溯方法求解，首先要分析問題的求解空間。可用一棵n叉樹表示這個問題的求解空間，在回溯周遊這個課二叉樹的過程中形成合理的解。

對于這棵n叉樹，列序号i（0~n-1）是它的孩子，而每個孩子都有深度為n的子樹（包括自身），這些子樹的層次是n個皇後（也代表每個皇後的行序号，因為不同的皇後肯定不在同一行）。于是，周遊這個n叉樹的每個孩子結點到葉子節點便得到一個合了解。周遊時，先從第一個孩子（第一行）開始周遊，深度周遊這個孩子子樹，直到找到（1）一個合了解或者（2）剪去不存在合了解的分枝。對于（1）表明已經周遊到了葉子節點，亦即所有的皇後都找到了一個合理的位置，對于（2）表明在某個層次的皇後節點不能找到一個合理位置，于是停止深度周遊，将此分枝剪去。不管對于哪種情況，此時要向上層回溯，繼續探索合理的解。直到整個n叉樹都周遊完。

比如對于4個皇後的情況，首先讓第一個皇後占據x[0][0](第一行第一列)，然後讓第二個皇後在第二行尋找合适的位置x[1][2](第二行，第3列)，第三個皇後在第三行尋找合适的位置，此時第三個皇後已經不能找到合适位置，于是将此分枝剪去。回溯到第二個皇後（第二行），探索新的位置，此時對于第二個皇後已經不能找到合理位置。回溯到第一個皇後（第一行），探索新的位置。此時，讓第一個皇後占據第一行第二列x[0][1]，依次回溯，直到第一個皇後的所有列都試探完畢，也就周遊完了n叉樹。

下面給出遞歸和非遞歸的實作：

遞歸實作：

1 #include <stdio.h>

2 #include <stdlib.h>

3 #include <math.h>

4 #define N 8

5

6 int x[N];//x[i]代表第i個皇後的列序号，行序号是下标i

7 int sum;

8 bool place(int i)

9 {

10 int j=0;

11 for(j =0;j<i;j++)

12 if(abs(x[i]-x[j]) == abs(i-j)|| x[j] == x[i])

13 return false;

14 return true;

15 }

16 void back_queen(int t)

17 {

18 int i =0;

19 if(t>N-1)

20 sum++;

21 else

22 {

23 for(i=0;i<N;i++)//探索第t層(第t個皇後)的所有列号

24 {

25 x[t]=i;

26 if(place(t))

27 back_queen(t+1);

28 x[t]=0;

29 }

30 }

31 }

32 int main()

33 {

34 back_queen(0);

35 printf("sum = %d/n",sum);

36 }

~ 疊代實作：

1 #include <stdio.h>

2 #include <stdlib.h>

3 #define N 8

4

5 int x[N];

6 int sum;

7 bool place(int i)

8 {

9 int j=0;

10 for(j =0;j<i;j++)

11 if(abs(x[i]-x[j]) == abs(i-j)|| x[j] == x[i])

12 return false;

13 return true;

14 }

15 void queen()

16 {

17 x[0]=-1;//初始化第一個皇後的坐标，在第一行第一列

18 int k = 0;//表示列号

19 while(k>=0)

20 {

21 x[k]+=1;//此時對于第k個皇後，列号向右移動，表示，當回溯到這一層時0~x[k]-1已經探索過了，接着往後探索

22 while(x[k]<N && !place(k)) x[k]++;//對于第k個皇後，找到一個合适的位置

23 if(x[k]<N)

24 {

25 if(k==N-1)

26 sum ++;//如果k已經是最後一個皇後，則找到了一個方案

27 else// 否則，繼續探索下一個皇後

28 {

29 k++;

30 x[k] = -1;

31 }

32 }

33 else//對于第k個皇後，沒有找到一個合适的位置，這相對于搜尋樹的第k層，于是對于這個節點的子樹不再搜尋,回溯到上一層

34 k--;

35 }

36 }

37 int main()

38 {

39 queen();

40 printf("sum = %d/n",sum);

41 }