华师一附中OI组

标题: 8Queen问题 [打印本页]

---

作者: diggersun    时间: 2015-2-8 10:13
标题: 8Queen问题
8Queen 简易程序
void mysearch(int i);   搜索第I个皇后放在第I行的哪一列
{  int j,k;
   if (i>=8)  输出A数组
   else  for(k=0;k<=7;k++)
          if 能放下 {a[i]=k;mysearch(i+1);}
}
bool canplace (i,j) 能放下函数，判断第I行能否放在第J列
{
    for(k=0;k<i;k++)
     {if (a[k]==j) canplace=false  表示有某个和他一列
     if (i-k)/(j-a[k])=+-1  canpalce=false}
}


一个位置被占用，符合三条线的不能被选
1、列   若a[i]=x，则所有的B1[x] 不能被选
2、正对角线  向右下  
       a[i]=x  a[k]=y 请问这四个变量有什么关系  8+i-x=8+k-y  b2[i-x]不能被选  纠正一下 偏移问题
3、反对角线  向右上
       a[i]=x  a[k]=y 请问这四个变量有什么关系  i+x=k+y  b3[i+x]不能被选

int b1[8],b2[15],b3[15]

---

作者: diggersun    时间: 2015-2-8 10:52

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. int a[8];
   
5. int s;
   
6. bool canplace(int i,int j)
   
7. {
   
8.     int k;
   
9.     bool bb=true;
   
10.     for (k=0; k<=i-1; k++)
    
11.         if (a[k]==j) bb=false;
    
12.         else if (abs(i-k)==abs(j-a[k])) bb=false;
    
13.     return bb;
    
14. }
    
15. void mysearch(int i)
    
16. {
    
17.     int j,k;
    
18.     if (i==8)
    
19.     {
    
20.         cout<<' '<<s++<<':';
    
21.         for (j=0; j<=7; j++)cout<<a[j];
    
22.         cout<<endl;
    
23.     }
    
24.     else for (k=0; k<=7; k++)
    
25.             if (canplace(i,k))
    
26.             {
    
27.                 a[i]=k;
    
28.                 mysearch(i+1);
    
29.             }
    
30. }
    
31. int main()
    
32. {
    
33.     mysearch(0);
    
34.     return 0;
    
35. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2