N皇後問題

java實作：

注解都在代碼裡了！

package agother;

import java.util.Arrays;

public class Queen {
    /*
     * 為了友善，二維矩陣的0行0列設為哨兵，不會正真使用
     * aux為輔助數組，數組的頭和尾均設為哨兵，是以數組長度為n+2
     * deep為試探層
     * aux[deep]為deep層的皇後在deep層的位置
     * */
    public static int queenOfN(int n){
        int count = 0;
        int[][] ary = new int[n+1][n+1];
        int[] aux = new int[n+2];
        int deep = 1;//從第一層開始
        while(deep>0){
            if (deep > n) {//有解
                deep--;
                count++;
            }else {//能夠到deep層，有可能是從deep-1層試探而來，也有可能是從deep+1回溯而來
                aux[deep] += 1;//因為有哨兵的作用，總是可以從aux[deep]的下一個位置開始
                while(aux[deep] <= n){//在deep層進行枝剪
                    if (check(aux, deep)) {//deep層的aux[deep]列符合條件
                        deep++;//試探到下一層
                        aux[deep] = 0;//重置下一層的初始位置
                        break;
                    }else {//deep層的aux[deep]列不符合條件
                        aux[deep] += 1;
                    }
                }
                if (aux[deep] >= n) {deep--;}//回溯到上一層
            }
        }
        return count;
    }
    /*
     * 因為試探的過程是逐層往下的，是以行沖突不會發生
     * aux[i] == aux[k]會引起類沖突
     * Math.abs(i-k) == Math.abs(aux[i]-aux[k]會引起正反對角線沖突
     * */
    private static boolean check(int[] aux,int k){
        for (int i = 1; i < k; i++) {
            if (Math.abs(i-k) == Math.abs(aux[i]-aux[k]) || aux[i] == aux[k]){
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            int count = queenOfN(8);
            System.out.println(count);
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
    }

}