[51. N-Queens] #leetcode

51_0827.java

public class Solution {
    private static int[] res;
    private static List<List<String>> sol;
    
    public List<List<String>> solveNQueens(int n) {
        res = new int[n];
        sol = new ArrayList<>();
        if (n == 0) {
            sol.add(new ArrayList<String>());
            return sol;
        }
        DFS(0, n);
        return sol;
    }
    
    private static void DFS(int row, int n) {
        for (int col = 0; col < n; col++ ) {
            boolean ok = true;
            for (int i = 0; i < row; i++) {
                if (col == res[i] || Math.abs(col - res[i]) == Math.abs(i - row)) {
                    ok = false;
                    break;
                }
            }
            
            if (!ok) continue;
            res[row] = col;
            
            if (row == n - 1) {
                addResult();
            } else {
                DFS(row+1, n);
            }
        }
    }
    
    private static void addResult() {
        List<String> tmp = new ArrayList<>();
        for (int r : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < res.length; i++) {
                if (r == i) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            tmp.add(sb.toString());
        }
        sol.add(tmp);
    }
}