个人技术分享

方案一、递推

递推 + 回溯

public class NQueen {
    private static final int N = 4;

    public static void main(String[] args) {
        int  i, count = 1;
        int[] pos = new int[N + 1];
        i = 1;
        while (i >= 1) {
            pos[i]++;
            while (pos[i] <= N && !isPlace(pos, i)) {
                pos[i]++;
            }
            if (pos[i] <= N && i == N) {//打印
                System.out.println("方案：" + count++);
                print(pos);
            }
            if (pos[i] <= N && i < N) {//考虑下一个皇后
                i++;
            } else {
                pos[i] = 0;
                i--;
            }
        }
    }

    private static void print(int[] pos) {
        for (int i = 1; i < N; i++) {
            System.out.print(pos[i] + ",");
        }
        System.out.println(pos[N]);
    }

    /**
     * 第k个皇后是否与前面冲突
     */
    private static boolean isPlace(int pos[], int k) {
        for (int i = 1; i < k; i++) {
            if (pos[i] == pos[k] || k - i == Math.abs(pos[i] - pos[k])) {
                return false;
            }
        }
        return true;
    }
}

方案二、递归

public class NQueen {
    private static final int N = 4;
    private static final int[] queen = new int[N + 1];

    public static void main(String[] args) {
        nQueen(1);
    }

    private static void nQueen(int j) {
        for (int i = 1; i <= N; i++) {
            queen[j] = i;
            if (isPlace(j)) {
                if (j == N) {
                    print();
                } else {
                    nQueen(j + 1);
                }
            }
        }
    }

    private static void print() {
        for (int i = 1; i < N; i++) {
            System.out.print(queen[i] + ",");
        }
        System.out.println(queen[N]);
    }

    /**
     * 第k个皇后是否与前面冲突
     */
    private static boolean isPlace(int k) {
        for (int i = 1; i < k; i++) {
            if (queen[i] == queen[k] || k - i == Math.abs(queen[i] - queen[k])) {
                return false;
            }
        }
        return true;
    }
}