八皇后问题

gaokanghao

错在哪?

1. #include<iostream>
   
2. int sum,f[9];
   
3. bool a[16],b[9],c[16];
   
4. using namespace std;
   
5. int dfs(int step);
   
6. void print();
   
7. int main()
   
8. {
   
9.         dfs(1);
   
10.         return 0;
    
11. }
    
12. int dfs(int step)
    
13. {
    
14.         int i;
    
15.         for(i=1;i<=8;i++)
    
16.         {
    
17.                 if((!a[i])&&(!b[i+step])&&(!c[i-step+7]))
    
18.                 {
    
19.                         f[step]=i;
    
20.                         a[i]=true;
    
21.                         b[i+step]=true;
    
22.                         c[step-i+7]=true;
    
23.                         if(i==8)
    
24.                         {
    
25.                                 print();
    
26.                         }
    
27.                         else
    
28.                         {
    
29.                                 dfs(step+1);
    
30.                         }
    
31.                         a[i]=false;
    
32.                         b[i+step]=false;
    
33.                         c[step-i+7]=false;
    
34.                 }
    
35.         }
    
36. }
    
37. void print()
    
38. {
    
39.         int i;
    
40.         sum++;
    
41.         cout<<"sum="<<sum<<endl;
    
42.         for(i=1;i<=8;i++)
    
43.         {
    
44.                 cout<<f[i];
    
45.         }
    
46.         cout<<endl;
    
47. }

复制代码

magshines

1，不知道print属不属于关键字，先确认下吧
2，dfs函数for循环的时候b超限了，i为8，step为1，出现了b[9]
3，sum未初始化，sum++有什么意义

xd_ydchen

我想 dfs 函数改成这个样子是可以的

1. 
   
2. int dfs(int step)
   
3. {
   
4.     int i;
   
5.     bool g[9] = {0};
   
6.     for (i = 1; i < step; i++)
   
7.     {
   
8.         /* unusable grids */
   
9.         int res = f[i];
   
10.         g[res]=true;
    
11.         
    
12.         int diff_line = step - i;
    
13.         if (res - diff_line >= 1 && res - diff_line <= 8)
    
14.             g[res - diff_line]=true;
    
15.         if (res + diff_line >= 1 && res + diff_line <= 8)
    
16.             g[res + diff_line]=true;
    
17.     }
    
18.     for(i = 1; i <= 8; i++)
    
19.     {
    
20.         if(!g[i])
    
21.         {
    
22.             f[step]=i;
    
23.             if(step==8) /*last step*/
    
24.             {
    
25.                 print();
    
26.             }
    
27.             else
    
28.             {
    
29.                 dfs(step+1);
    
30.             }
    
31.         }
    
32.     }
    
33. }
    

复制代码

xd_ydchen

1. int dfs(int step)
   
2. {
   
3.     int i;
   
4.     for(i=1;i<=8;i++)
   
5.     {
   
6.         bool able = true;
   
7.         for (int st = 1; st < step; st++)
   
8.         {
   
9.             int diff = step - st;
   
10.             if (f[st] == i || f[st] + diff == i || f[st] - diff == i)
    
11.             {
    
12.                 able = false;
    
13.                 break;
    
14.             }
    
15.         }
    
16.         if(able)
    
17.         {
    
18.             f[step]=i;
    
19.             if(step==8)
    
20.             {
    
21.                 print();
    
22.             }
    
23.             else
    
24.             {
    
25.                 dfs(step+1);
    
26.             }
    
27.         }
    
28.     }
    
29. }

复制代码

zyj8691

好东西，多谢分享