Leetcode - N-Queens

[分析] N皇后摆放规则：两个皇后不能共存于同一行、同一列以及同一（斜率为1的）斜线上。rows 数组用于记录每行的皇后所摆放的列位置，并用于构造结果；cols数组记录该列为哪个皇后的地盘，两个数组共同完成回溯过程。

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[] rows = new int[n]; // rows[i] = j, means board[i][j] = Q
        int[] cols = new int[n]; // cols[j] = i, means board[i][j] = Q
        for (int i = 0; i < n; i++) {
            rows[i] = -1;
            cols[i] = -1;
        }
        List<List<String>> result = new ArrayList<List<String>>();
        recur(n, 0, rows, cols, result);
        return result;
    }
    
    public void recur(int n, int r, int[] rows, int[] cols, List<List<String>> result) {
        if (r == n) {
            List<String> oneSolution = new ArrayList<String>();
            StringBuilder rowstr = new StringBuilder(n);
            for (int i = 0; i < n; i++) {
                rowstr.delete(0, n);
                for (int j = 0; j < n; j++) {
                    if (rows[i] != j)
                        rowstr.append('.');
                    else
                        rowstr.append('Q');
                }
                oneSolution.add(rowstr.toString());
            }
            result.add(oneSolution);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (cols[j] == -1 && verifyDiagnal(rows, r, j)) {
                rows[r] = j;
                cols[j] = r;
                recur(n, r + 1, rows, cols, result);
                rows[r] = -1;
                cols[j] = -1;
            }
        }
    }
    
    public boolean verifyDiagnal (int[] rows, int r, int c) {
        for (int i = 0; i < r; i++) {
            if (r - i == Math.abs(c - rows[i]))
                return false;
        }
        return true;
    }
}