51 N-Queens

51. N-Queens

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 integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.

Example:

Input: 4

Output:
 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
 ]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

2. Implementation

(1) Backtracking

思路: 我们对每一行的所有列都尝试摆放queen, 通过三个boolean数组cols, diagnol1, diagnol2分别判断在当前位置的同一列，主对角线和副对角线的位置上是否已经有queen。比较tricky的地方是主对角线和副对角线上怎么判断是否已经有Queen摆放，通过观察我们发现，同一个主对角线上的数的位置都等于 row - col, 为了避免负数出现，我们加上n，即row - col + n, 副对角线上都等于row + col

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        String[] board = new String[n];
        boolean[] cols = new boolean[n];
        boolean[] diagnol1 = new boolean[2 * n];
        boolean[] diagnol2 = new boolean[2 * n];
        recSolveNQueens(0, n, cols, diagnol1, diagnol2, board, res);
        return res;
    }

    public void recSolveNQueens(int row, int n, boolean[] cols, boolean[] diagnol1, boolean[] diagnol2, String[] board, List<List<String>> res) {
        if (row == n) {
            res.add(convertToList(board));
            return;
        }

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

            if (cols[col] || diagnol1[index1] || diagnol2[index2]) {
                continue;
            }
            char[] rowArr = new char[n];
            Arrays.fill(rowArr, '.');
            rowArr[col] = 'Q';
            board[row] = new String(rowArr);
            cols[col] = true;
            diagnol1[index1] = true;
            diagnol2[index2] = true;
            recSolveNQueens(row + 1, n, cols, diagnol1, diagnol2, board, res);
            diagnol2[index2] = false;
            diagnol1[index1] = false;
            cols[col] = false;
        }
    }

    public List<String> convertToList(String[] board) {
        List<String> res = new ArrayList();

        for (String row : board) {
            res.add(row);
        }
        return res;
    }
}

3. Time & Space Complexity

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