Posted on 2010-08-22 21:19
lzh525 阅读(3027)
评论(0) 编辑 收藏 引用 所属分类:
数据结构及算法问题
1 /*
2
3 N皇后问题算法思想
4
5 由于这是一个平面上棋子布局处理问题，因此，我们可以将问题看成是一个二维数组问题。给八个皇后分别编号为1,2，…,8，其中第i个皇后放置在第i行上，并这就解决了不同皇后分别摆放在不同列的问题，这样又可以把问题简化为一个一维数组的问题，假设用一维数组arr来存放皇后所放置的列，对于第i个皇后，假设它存放在arr[i]列上，则对应的arr数组应满足如下的条件：[2]
6 (1) 因为一共只有8列，故a[i]的取值只能取1到8之间的数。
7 (2) 因为不同的皇后只能放在不同的列上，则对于任意的i和j，应满足如果i!=j，则a[i]!=a[j]
8 (3) 因为不同的皇后不能存放在同一对角线上，故连接两个皇后的直线的斜率应不能等于正负1，而连接任意第i个皇后和第j个皇后(i与j不同)的直线的斜率的计算公式为：(a[i]-a[j])/(i-j),即(a[i]-a[j])/(i-j)！=±1，即
9 |a[i]-a[j]|!=| i-j |
10
11 */
12 #include<iostream>
13 #include<math.h>
14 using namespace std;
15 const MAX=1000;
16 long count;
17 bool is_a_solution(long k,long n)
18 {
19 return (k==n);
20 }
21 void process()
22 {
23 count++;
24 }
25 void construct_candidates(long *a,long k,long n,long *c,long &ncandidates)
26 {
27 long i,j;
28 bool legal_move;//是否为可选位置的标记
29 ncandidates=0;//可选位置的个数
30 for(i=1;i<=n;i++)//搜索第k行的皇后可选的范围(列)
31 {
32 legal_move=true;
33 for(j=1;j<k;j++)//第k行之前放置的皇后攻击的范围
34 {
35 if(abs(k-j)==abs(i-a[j])) //斜线攻击!!!第j行的皇后位置(j,a[j]),待放置的位置(k,i)(斜率为+-1)
36 legal_move=false;
37 else if(i==a[j]) //直线攻击!
38 legal_move=false;
39 }
40 if(legal_move==true)
41 {
42 c[ncandidates]=i;//第k行的皇后可放置在第k行的第i列
43 ncandidates=ncandidates+1;
44 }
45 }
46 }
47 void backtrack(long *a,long k,long n)
48 {
49 long c[MAX];
50 long ncandidates;
51 long i;
52 if(is_a_solution(k,n))
53 process();
54 else
55 {
56 k++;
57 construct_candidates(a,k,n,c,ncandidates);
58 for(i=0;i<ncandidates;i++)
59 {
60 a[k]=c[i]; //k 从1 开始变起
61 backtrack(a,k,n);
62 }
63 }
64 }
65 int main()
66 {
67 long a[MAX],n;
68 while(cin>>n)
69 {
70 if(n==0)
71 break;
72 count=0;
73 backtrack(a,0,n);
74 cout<<"n="<<n<<" solution_count="<<count<<endl;
75 }
76 return 0;
77 }
78