8皇后问题

image.png

首先，可归纳问题的条件为，8皇后之间需满足：
1.不在同一行上
2.不在同一列上
3.不在同一斜线上
4.不在同一反斜线上
第一种方法：
先全排列，然后再判断每个排列是否满足8皇后的要求
先定义数组c[8]初始化分别为0-7
c[i]表示第i行第c[i]列

public class Pass { 
     HashSet<int[]> set = new HashSet<int[]>();
     public void Permutation(int[] c,int begin){
            if(c.length==0)
                return;
            if(begin==c.length-1){
                if(judge(c)){//判断是否符合8皇后需求，如果符合就输出该排列
                    for(int k=0;k<c.length;k++){
                        System.out.print(c[k]);
                    }
                    System.out.println();
                }               
            }else{
                for(int i=begin;i<c.length;i++){                
                        Swap(c,i,begin);
                        Permutation(c,begin+1);//固定好当前一位，继续排列后面的
                        Swap(c,i,begin);                                                                
                }
            }           
        }
     public boolean judge(int[] c){
         for(int i=0;i<c.length;i++){
             for(int j=i+1;j<c.length;j++){
                 if(Math.abs(i-j)==Math.abs(c[i]-c[j])){//任意两个皇后肯定是不同列，所以只需判断是否在同一对角线上
                     return false;
                 }
             }
         }
         return true;
     }
    public void Swap(int[] c,int i,int begin){
        if(i!=begin){
            int temp=c[i];
            c[i]=c[begin];
            c[begin]=temp;
        }       
    }       
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        Pass ps=new Pass();
        int[] c={0,1,2,3,4,5,6,7};
        ps.Permutation(c,0);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间："+(endTime-startTime)+"毫秒");
    }  
}

方法一 的效率比较低，方法二采用回溯算法

public class Test2 {    
    int n=8;//n皇后问题
    int[] x=new int[n+1];//x[i]表示皇后i放在第i行第x[i]列
    public void backTrace(int t){
        if(t>n){
            print();
            System.out.println();
            return;
        }else{
            for(int i=1;i<=n;i++){
                x[t]=i;
                if(judge(t)){
                    backTrace(t+1);
                }
            }
        }       
    }
    public boolean judge(int t){
        for(int j=1;j<t;j++){
            if((Math.abs(t-j))==(Math.abs(x[t]-x[j]))||(x[j])==x[t])
                return false;//如果在同一行同一列或同一斜线上，返回false
        }
        return true;
    }
    public void print(){
        for(int i=1;i<x.length;i++){
            System.out.print("皇后"+i+"在"+i+"行"+x[i]+"列、");
        }
    }
    public static void main(String[] args){
        long startTime = System.currentTimeMillis();
        Test2 test=new Test2();
        test.backTrace(1);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间："+(endTime-startTime)+"毫秒");
    }       
}