August 18, 2019

51. N-Queens

Recursion (backtracking).

在放置的时候，要保持当前的状态为合法，即当前放置位置的同一行、同一列、两条对角线上都不存在皇后。

用一个一位数组来存放当前皇后的状态
int A[N] stores the current solution on each row.
A[8] = {1, 3, 5, 7, …}
1 means the 1st queen is put on the 1st column of the 1st row.
3 means the 2nd queen is put on the 3rd column of the 2nd row.

判断列是否冲突，只需要看state数组中state[0…k-1] 是否有和state[k]相等；
判断对角线是否冲突：如果两个皇后在同一对角线，那么|row1-row2| = |column1 - column2|，（row1，column1），（row2，column2）分别为冲突的两个皇后的位置摘抄

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        solveNQueensHelper(n, cur, res);
        return res;
    }
    
    private void solveNQueensHelper(int n, List<Integer> cur, List<List<String>> res) {
        // base case: for all rows, we know where the queen is positioned
        if (n == cur.size()) {
            List<String> curQueen = putOnBoard(cur);
            res.add(curQueen);
            return;
        }
        for (int i = 0; i < n; i++) {
            // check if putting a queen at column i at current row is valid
            if (isValid(i, cur)) {
                cur.add(i);
                solveNQueensHelper(n, cur, res);
                cur.remove(cur.size() - 1);
            }
        }
    }
    
    private boolean isValid(int col, List<Integer> cur) {
        int row = cur.size();
        for (int i = 0; i < row; i++) {
            if (cur.get(i) == col || Math.abs(cur.get(i) - col) == row - i) {
                return false;
            }
        }
        return true;
    }
    
    private List<String> putOnBoard(List<Integer> cur) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < cur.size(); i++) {
            StringBuilder sb = new StringBuilder();
            int pos = cur.get(i);
            for (int j = 0; j < pos; j++) {
                sb.append(".");
            }
            sb.append("Q");
            for (int j = pos + 1; j < cur.size(); j++) {
                sb.append(".");
            }
            res.add(sb.toString());
        }
        return res;
    }
}