N-Queens I && II

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

DFS:

public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> res = new ArrayList<String[]>();
        int[] rows = new int[n];
        solve(res, rows, 0);
        return res;
    }
    
    private void solve(ArrayList<String[]> res, int[] rows, int row) {
        if (row == rows.length) {
            String[] tmp = new String[rows.length];
            draw(rows, tmp);
            res.add(tmp);
            return;
        }
        
        for (int i = 0; i < rows.length; i++) {
            rows[row] = i;
            if (valid(rows, row)) {
                solve(res, rows, row + 1);
            }
        }
    }
    
    private boolean valid(int[] rows, int row) {
        for (int i = 0; i < row; i++) {
            if (rows[i] == rows[row]) {
                return false;
            }
            
            if (Math.abs(rows[row] - rows[i]) == Math.abs(row - i)) {
                return false;
            }
        }
        return true;
    }
    
    private void draw(int[] rows, String[] tmp) {
        for (int i = 0; i < tmp.length; i++) {
            StringBuilder cur = new StringBuilder();
            int pos = rows[i];
            for (int j = 0; j < pos; j++) {
                cur.append('.');
            }
            cur.append('Q');
            for (int j = pos + 1; j < tmp.length; j++) {
                cur.append('.');
            }
            tmp[i] = cur.toString();
        }
    }
}

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

经典的递归问题。用一个cols[]数组，cols[i]: i代表第几列，cols[i]代表在第i列的行数。同时还要检查在当前列当前行和之前比较是否合法。

public class Solution {
    //Time: O(n^n)  Space: O(n)
    private int num = 0;
    public int totalNQueens(int n) {
        int[] cols = new int[n];
        Nqueen(cols, 0);
        return num;
    }
    
    private void Nqueen(int[] cols, int col) {
        if (col == cols.length) {
            num++;
            return;
        }
        
        for (int i = 0; i < cols.length; i++) {
            cols[col] = i;
            if (valid(cols, col)) {
                Nqueen(cols, col + 1);
            }
        }
    }
    
    private boolean valid(int[] cols, int col) {
        for (int i = 0; i < col; i++) {
            if (cols[i] == cols[col]) {
                return false;
            }
            if (Math.abs(cols[col] - cols[i]) == Math.abs(col - i)) {
                return false;
            }
        }
        return true;
    }
}