Ka的回溯编程练习 Part2|八皇后问题和N皇后问题

 1 #include <stdio.h>
 2 int AChessBlockRecorder[10]={0}/*下标层数，内容竖行*/,ThisIsMyPlace[10]={0};/*占领*/
 3 int TheTalentOfTheQueen1[25]={0};  //前一个维度代表主对角线特性,相减同
 4 int TheTalentOfTheQueen2[25]={0};
 5 int total=0;
 6 void output()
 7 {
 8     total++;
 9     printf("solotion:<%d>---
",total);
10     int q,w;
11     for(q=1;q<9;q++)
12     {
13         for(w=1;w<9;w++)
14                 AChessBlockRecorder[q]==w?printf("☆"):printf("★");
15         printf("
");
16     }        
17 }
18 int search(int n)
19 {
20     int i;
21     for(i=1;i<=8;i++)
22     {
23         if(ThisIsMyPlace[i]==0&&TheTalentOfTheQueen1[i-n+8]==0&&TheTalentOfTheQueen2[i+n]==0) //此竖行尚未被皇后占领 
24         {
25             AChessBlockRecorder[n]=i;
26             ThisIsMyPlace[i]=1;
27             TheTalentOfTheQueen1[i-n+8]=1;
28             TheTalentOfTheQueen2[i+n]=1;
29             if(n==8) output();
30             else search(n+1);
31             TheTalentOfTheQueen1[i-n+8]=0;
32             TheTalentOfTheQueen2[i+n]=0;
33             ThisIsMyPlace[i]=0; 
34         }
35     }
36 }
37 int main()
38 {
39     freopen("o.txt","w",stdout);
40     search(1);
41     return 0;
42 }

算是回溯中比较基本的了。

N皇后就是把数字改一改，注释比较多就不做详细解释了

 1 #include <stdio.h>
 2 #define MAXN 20
 3 int AChessBlockRecorder[MAXN+2]={0}/*下标层数，内容竖行*/,ThisIsMyPlace[MAXN+2]={0};/*竖行占领*/
 4 int TheTalentOfTheQueen1[MAXN+20]={0};  //代表主对角线占领,坐标相减数值相同
 5 int TheTalentOfTheQueen2[MAXN+20]={0};  //副对角线，相加相同 
 6 int total=0;
 7 void output()
 8 {
 9     total++;
10     printf("solotion:<%d>---
",total);
11     int q,w;
12     for(q=1;q<MAXN+1;q++)
13     {
14         for(w=1;w<MAXN+1;w++)
15                 AChessBlockRecorder[q]==w?printf("☆"):printf("★");
16         printf("
");
17     }        
18 }
19 int search(int n)
20 {
21     int i;
22     for(i=1;i<=MAXN;i++)
23     {
24         if(ThisIsMyPlace[i]==0&&TheTalentOfTheQueen1[i-n+MAXN]==0&&TheTalentOfTheQueen2[i+n]==0) //此竖行、对角线尚未被皇后占领 
25         {
26             AChessBlockRecorder[n]=i; //记录盘记录位置 
27             ThisIsMyPlace[i]=1;
28             TheTalentOfTheQueen1[i-n+MAXN]=1;  //i-n可能越位，加上一个数保证不会越位 
29             TheTalentOfTheQueen2[i+n]=1;
30             if(n==MAXN) output();
31             else search(n+1);
32             TheTalentOfTheQueen1[i-n+MAXN]=0;
33             TheTalentOfTheQueen2[i+n]=0;
34             ThisIsMyPlace[i]=0;   //以上都是回溯框架 
35         }
36     }
37 }
38 int main()
39 {
40     freopen("o.txt","w",stdout); //注意，20比较作死，300000+种解的时候第一层的皇后还没挪位子 
41     search(1);
42     return 0;
43 }