Java N皇后问题详细解题思路

Question

有一个n*n的棋盘，上面有n个皇后。使每个皇后不能互相攻击，有多少种摆法？
样例输入：

10

样例输出：

27

求解题思路

Answer 1

试试这个

public class Queen {
    private int n;
    private int[] result;
    private int count;

    public Queen(int n) {
        this.n = n;
        result = new int[n];
    }

    public void getResult() {
        calQueens(0);
        System.out.println("一共有" + count + "种摆法");
    }

    private void calQueens(int row) {
        if (row == n) {
            count++;
            printQueens(result);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isOk(row, col)) {
                result[row] = col;
                calQueens(row + 1);
            }
        }
    }

    private boolean isOk(int row, int col) {
        int leftup = col - 1, rightup = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            if (result[i] == col) return false;
            if (leftup >= 0) {
                if (result[i] == leftup) return false;
            }
            if (rightup < n) {
                if (result[i] == rightup) return false;
            }
            leftup--;
            rightup++;
        }
        return true;
    }

    private void printQueens(int[] result) {
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (result[row] == col) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Queen queen = new Queen(4);
        queen.getResult();
    }
}