52 N-Queens II

52. N-Queens II

1. Question

The n-queens puzzle is the problem of placing n _queens on an _n × _n _chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

2. Implementation

(1) Backtracking

class Solution {
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }

        int[] res = new int[n];
        boolean[] cols = new boolean[n];
        boolean[] diagnol1 = new boolean[2 * n];
        boolean[] diagnol2 = new boolean[2 * n];
        getTotalNQueens(0, n, cols, diagnol1, diagnol2, res);
        return res[0];
    }

    public void getTotalNQueens(int row, int n, boolean[] cols, boolean[] diagnol1, boolean[] diagnol2, int[] res) {
        if (row == n) {
            ++res[0];
            return;
        }

        for (int col = 0; col < n; col++) {
            int index1 = row - col + n;
            int index2 = row + col;

            if (cols[col] || diagnol1[index1] || diagnol2[index2]) {
                continue;
            }

            cols[col] = true;
            diagnol1[index1] = true;
            diagnol2[index2] = true;
            getTotalNQueens(row + 1, n, cols, diagnol1, diagnol2, res);
            cols[col] = false;
            diagnol1[index1] = false;
            diagnol2[index2] = false;
        }
    }
}

3. Time & Space Complexity

时间复杂度O(n * 2 ^ n), 每一行里只能放一个queen, 每一列只有放和不放两种可能，所以n * 2 ^ n，空间复杂度O(n)