八皇后问题

luckin

1. #include<stdio.h>
   
2. 
   
3. int count = 0;
   
4. 
   
5. int notdanger(int row,int j,int (*chess2)[8])
   
6. {
   
7.         int i,k,flag=0,flag1=0,flag2=0,flag3=0,flag4=0;
   
8.         //列方向
   
9.         for(i=0;i<8;i++)
   
10.         {
    
11.                 if(*(*(chess2+i)+j))
    
12.                 {
    
13.                         flag=1;
    
14.                         break;
    
15.                 }
    
16.         }
    
17.         //左上方向
    
18.         for(i=row,k=j;i>=0&&k>=0;i--,k--)
    
19.         {
    
20.                 if(*(*(chess2+i)+k))
    
21.                 {
    
22.                         flag1=1;
    
23.                         break;
    
24.                 }
    
25.         }
    
26.         //右下方向
    
27.         for(i=row,k=j;i<8&&k<8;i++,k++)
    
28.         {
    
29.                 if(*(*(chess2+i)+k))
    
30.                 {
    
31.                         flag2=1;
    
32.                         break;
    
33.                 }
    
34.         }
    
35.         //左下方向
    
36.         for(i=row,k=j;i>=0&&k<8;i--,k++)
    
37.         {
    
38.                 if(*(*(chess2+i)+k))
    
39.                 {
    
40.                         flag3=1;
    
41.                         break;
    
42.                 }
    
43.         }
    
44.         //右上方向
    
45.         for(i=row,k=j;i<8&&k>=0;i++,k--)
    
46.         {
    
47.                 if(*(*(chess2+i)+k))
    
48.                 {
    
49.                         flag4=1;
    
50.                         break;
    
51.                 }
    
52.         }
    
53.         if(flag||flag1||flag2||flag3||flag4)
    
54.                 return 0;
    
55.         else
    
56.                 return 1;
    
57. }
    
58. //row表示起始行，n表示列数，最后一个参数表示指向棋盘每一行的指针。
    
59. void EightQueen(static int row,int n,int (*chess)[8])
    
60. {
    
61.         int chess2[8][8];
    
62.         int i,j;
    
63.         for(i=0;i<8;i++)
    
64.                 for(j=0;j<8;j++)
    
65.                         chess2[i][j]=chess[i][j];
    
66. 
    
67.                 if(8==row)
    
68.                 {
    
69.                         printf("第%d种方法为\n",count+1);
    
70.                         for(i=0;i<8;i++)
    
71.                         {
    
72.                                 for(j=0;j<8;j++)
    
73.                                 {
    
74.                                         printf("%d ",chess2[i][j]);
    
75.                                 }
    
76.                                 printf("\n");
    
77.                         }
    
78.                         count++;
    
79.                         printf("\n");
    
80.                 }
    
81.                 else
    
82.                 {
    
83.                         for(j=0;j<n;j++)
    
84.                         {
    
85.                                 if(notdanger(row,j,chess2))
    
86.                                 {
    
87.                                         for( i=0; i < 8; i++ )
    
88.                                 {
    
89.                                         *(*(chess2+row)+i) = 0;
    
90.                                 }
    
91.                                         *(*(chess2+row)+j)=1;
    
92.                                         EightQueen(row+1,n,chess2);
    
93.                                 }
    
94.                                        
    
95.                         }
    
96.                
    
97.                 }
    
98. }
    
99. int main()
    
100. {
     
101.         int chess[8][8]={0};
     
102.         EightQueen(0,8,chess);
     
103.         printf("*****all is %d ways!*****\n",count);
     
104.         return 0;
     
105. }

复制代码

87行至90行 为什么添加这部分？不是初始化的时候所有元素已经是0了。
**********欢迎各位大神*********

santaclaus

                      for(j=0;j<n;j++)
                        {
                                if(notdanger(row,j,chess2))
                                {     
                                     //八皇后放置问题并不是只考虑当前位置能不能放1，即便当前位置可放，还要考虑当下一行
                                     //都不能放1时，该怎么办？为了解决这问题时，它采取一种“试放”的策略。即，先在当前位
                                     //置“试放"一个1，一旦出现下一行都不能放置时，就必须立即取消当前位置的这个1。不然
                                     //这个1会被保存下来。具体见以下分析：

                                     //红色部分的代码是将当前行清零，保证该行最多只能放一个1。如果不清零操作的话，
                                     // 由于蓝色那行代码是在当前行的第j列置1的。如果出现下一行无论怎么放都是冲突的，
                                     //此时，当前位置的这个1就必须立即清理掉。不然，会随着j列从0到n的变化，该行1的
                                     //数量会越放越多，从而形成不了八皇后。   
                                     //其实这问题还有更好的解决方法，见我的贴子《回溯法求解八皇后问题的C语言实现》                              
                                      for( i=0; i < 8; i++ )
                                       {
                                              *(*(chess2+row)+i) = 0;
                                         }
                                       
                                        *(*(chess2+row)+j)=1;
                                        EightQueen(row+1,n,chess2);
                                }
                                       
                        }

luckin

santaclaus 发表于 2014-6-25 20:35

                               
登录/注册后可看大图

for(j=0;j

厉害！我调试的时候的row的值一直跳来跳去也是这个原因(回溯？)?

拈花小仙

santaclaus 发表于 2014-6-25 19:40
for(j=0;j

欢迎来交流http://bbs.fishc.com/group-264-1.html

繁空.星雨

顶一下