8皇后算法的简单实现（回溯）

package com.cai.learn.math;

/**
 * 8皇后问题运算（回溯算法）
 * 思路：1.第一个皇后放在第一行，第一列
 *      2.第二行皇后放在第二行第一列，然后判断是否OK，如不OK，继续放在第二列，第三列....第8列，找个一个合适的位置
 *      3.继续第三个皇后.....
 *      4.得到一个正确的时候，在栈回退到上一个栈时，就会开始回溯。即第一个皇后第一列时得到所有正确的解
 *      5.然后回头把第一个皇后放在第二列，第三列...第8列 得出所有正确解
 */
public class EightQueen {
    public static int count = 0;
    public static void main(String[] args) {
        //用数组存放 每行所在的位置
        int[] array = new int[8];
        getResult(array,0);
        System.out.printf("一共有%d种算法",count);//一共有92种算法

    }
    public static void getResult(int[] array,int n){
        if(n==8){
            count++;
            for (int i = 0; i < 8; i++) {
                System.out.print(array[i]+"\t");
            }
            System.out.println();
            return;
        }
        //8列，第1列。第2列....第8列
        for (int i = 0; i < 8; i++) {
            array[n] = i;
            if(isRight(array,n)){
                getResult(array,n+1);
            }
        }

    }

    /**
     * 判断第n行的位置是否正确
     * @param arr 已经排列的位置
     * @param i 第几行(i可能是0)
     * @return
     */
    public static boolean isRight(int[] arr,int i){
        for (int k = 0; k < i; k++) {
            //同一列，同一斜线上为false
            if (arr[k]==arr[i]||Math.abs(i-k)==Math.abs(arr[i]-arr[k])){
                return false;
            }
        }
        return true;
    }
}
8皇后算法的简单实现（回溯）

推荐阅读
