八皇后问题与回溯算法

思路

对于八皇后的求解可采用回溯算法，从上至下依次在每一行放置皇后，进行搜索，若在某一行的任意一列放置皇后均不能满足要求，则不再向下搜索，而进行回溯，回溯至有其他列可放置皇后的一行，再向下搜索，直到搜索至最后一行，找到可行解，输出。

可以使用递归函数实现上述回溯算法，递归函数用于求解在某一行放置皇后，具体代码如下所示
。
代码
1.    #include <stdlib.h>
2.    #include <stdio.h>
3.   
4.    int m[8][8] = {0};//表示棋盘，初始为0，表示未放置皇后
5.    int num = 0;//解数目
6.   
7.    //对于棋盘前row-1行已放置好皇后
8.    //检查在第row行、第column列放置一枚皇后是否可行
9.    bool check(int row,int column)
10.   {
11.       if(row==1) return true;
12.       int i,j;
13.       //纵向只能有一枚皇后
14.       for(i=0;i<=row-2;i++)
15.       {
16.           if(m[i][column-1]==1) return false;
17.       }
18.       //左上至右下只能有一枚皇后
19.       i = row-2;
20.       j = i-(row-column);
21.       while(i>=0&&j>=0)
22.       {
23.           if(m[i][j]==1) return false;
24.           i--;
25.           j--;
26.       }
27.       //右上至左下只能有一枚皇后
28.       i = row-2;
29.       j = row+column-i-2;
30.       while(i>=0&&j<=7)
31.       {
32.           if(m[i][j]==1) return false;
33.           i--;
34.           j++;
35.       }
36.       return true;
37.   }
38.  
39.   //当已放置8枚皇后，为可行解时，输出棋盘
40.   void output()
41.   {
42.       int i,j;
43.       num++;
44.       printf("answer %d:/n",num);
45.       for(i=0;i<8;i++)
46.       {
47.           for(j=0;j<8;j++) printf("%d ",m[i][j]);
48.           printf("/n");
49.       }
50.   }
51.  
52.   //采用递归函数实现八皇后回溯算法
53.   //该函数求解当棋盘前row-1行已放置好皇后，在第row行放置皇后
54.   void solve(int row)
55.   {
56.       int j;
57.       //考虑在第row行的各列放置皇后
58.       for (j=0;j<8;j++)
59.       {
60.           //在其中一列放置皇后
61.           m[row-1][j] = 1;
62.           //检查在该列放置皇后是否可行
63.           if (check(row,j+1)==true)
64.           {
65.               //若该列可放置皇后，且该列为最后一列，则找到一可行解，输出
66.               if(row==8) output();
67.               //若该列可放置皇后，则向下一行，继续搜索、求解
68.               else solve(row+1);
69.           }
70.           //取出该列的皇后，进行回溯，在其他列放置皇后
71.           m[row-1][j] = 0;
72.       }
73.   }
74.  
75.   //主函数
76.   int main()
77.   {
78.       //求解八皇后问题
79.       solve(1);
80.       return 0;
81.   }