69. N-Queens

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res, cols = [], []                     # cols[r] = column of the queen in row r
        used_c, used_d1, used_d2 = set(), set(), set()
        def place(r):
            if r == n:
                res.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in cols])
                return
            for c in range(n):
                if c in used_c or r - c in used_d1 or r + c in used_d2:
                    continue                   # attacked
                cols.append(c); used_c.add(c); used_d1.add(r - c); used_d2.add(r + c)
                place(r + 1)
                cols.pop(); used_c.remove(c); used_d1.remove(r - c); used_d2.remove(r + c)
        place(0)
        return res

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        place(0, n, new int[n], new boolean[n], new boolean[2 * n], new boolean[2 * n], res);
        return res;
    }
    private void place(int r, int n, int[] cols, boolean[] col, boolean[] d1, boolean[] d2, List<List<String>> res) {
        if (r == n) {
            List<String> board = new ArrayList<>();
            for (int c : cols) { char[] row = new char[n]; Arrays.fill(row, '.'); row[c] = 'Q'; board.add(new String(row)); }
            res.add(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (col[c] || d1[r - c + n] || d2[r + c]) continue;   // attacked
            cols[r] = c; col[c] = d1[r - c + n] = d2[r + c] = true;
            place(r + 1, n, cols, col, d1, d2, res);
            col[c] = d1[r - c + n] = d2[r + c] = false;
        }
    }
}

class Solution {
    void place(int r, int n, vector<int>& cols, vector<bool>& col, vector<bool>& d1, vector<bool>& d2, vector<vector<string>>& res) {
        if (r == n) {
            vector<string> board;
            for (int c : cols) { string row(n, '.'); row[c] = 'Q'; board.push_back(row); }
            res.push_back(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (col[c] || d1[r - c + n] || d2[r + c]) continue;   // attacked
            cols[r] = c; col[c] = d1[r - c + n] = d2[r + c] = true;
            place(r + 1, n, cols, col, d1, d2, res);
            col[c] = d1[r - c + n] = d2[r + c] = false;
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> cols(n);
        vector<bool> col(n, false), d1(2 * n, false), d2(2 * n, false);
        place(0, n, cols, col, d1, d2, res);
        return res;
    }
};

function solveNQueens(n) {
  const res = [], cols = [], col = new Set(), d1 = new Set(), d2 = new Set();
  const place = r => {
    if (r === n) { res.push(cols.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))); return; }
    for (let c = 0; c < n; c++) {
      if (col.has(c) || d1.has(r - c) || d2.has(r + c)) continue; // attacked
      cols.push(c); col.add(c); d1.add(r - c); d2.add(r + c);
      place(r + 1);
      cols.pop(); col.delete(c); d1.delete(r - c); d2.delete(r + c);
    }
  };
  place(0);
  return res;
}