8 QUEENS - JAVA

FROM:http://www.cnblogs.com/qinyg/archive/2012/05/21/2512353.html


package sideway;

public class sideway {
public static int COLOM_NUMBER=9;
public static int X[]=new int[COLOM_NUMBER]; 
public static boolean  place(int k)//考察皇后k放置在X[k]列是否发生冲突
{
   int i;
   for(i=0;i<k;i++)
       if(X[k]==X[i]||Math.abs(k-i)==Math.abs(X[k]-X[i]))
           return false;
       return true;//true代表有冲突
}
public static void queue()
{
   int k;
   for(int i=0;i<COLOM_NUMBER;i++)
       X[i]=-1;    
   X[0]=(int) (Math.random() * 1000) % (COLOM_NUMBER);//X[0]为1和7的时候出错
   k=1;
   while(true)
   {

X[k]=X[k]+1;   //在下一列放置第k个皇后
   
       while(X[k]<COLOM_NUMBER && place(k)==false)
           X[k]=X[k]+1;//搜索下一列
       //成功得到一个结果，输出结果
       if(X[k]<COLOM_NUMBER && k==COLOM_NUMBER-1)
       {
        for(int i=0;i<COLOM_NUMBER;i++)
        System.out.print(X[i]+" ");
           System.out.println("succeed!");
return;
       }

       else 
if(X[k]<COLOM_NUMBER && k<COLOM_NUMBER-1)
k=k+1;//放置下一个皇后
else
{
X[k]=-1;//重置X[k],回溯,我觉得这称得上是sideway的思想，考虑的是列的local maximum！
k=k-1;
}
   }
}
public static void main(String[] args) {
// TODO Auto-generated method stub
queue();
System.out.println("done!");
}

}