八皇后问题--回溯法

import static java.lang.Math.abs;

public class EightQueue {
    int[] x = new int[9];
    static int sum = 0;
    public void queue(int n){
       int i,k;
       for(i=1;i<=n;i++){
           x[i]=0;
       }
       k=1;
       while(k>=1){ //如果回溯完，则k=0，循环结束。
           x[k]=x[k]+1; //在下一列放置第k个皇后
           while(x[k]<=n&&!place(k)){
               x[k]=x[k]+1;//搜索下一列
           }
           if(x[k]<=n&&k==n){//得到一个输出
               sum++;
               for(i=1;i<=n;i++){
                   System.out.print(x[i]);
               }
               System.out.println();
           }else if(x[k]<=n&&k<n){
               k=k+1;//放置下一个皇后
           }else
           {
               x[k]=0;//重置x[k],回溯  从第0列开始
               k=k-1;
           }
       }
    }
    boolean place(int k)//考察皇后k放置在x[k]列是否发生冲突
    {
        int i;
        for(i=1;i<k;i++) //i表示前1到k-1的每个棋子的比较
            if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))
                return false;
        return true;
    }

    public static void main(String[] args) {
        int n= 8;
        EightQueue eightQueue = new EightQueue();
        eightQueue.queue(n);
        System.out.println(sum);
    }
}

 

回溯法，不懂的可以通过debug调试，查看其过程。

x[k]=0的目的是，每行棋子都是从第1列开始的。

x[k]的值表示，第k行的棋子放在第几列。