N-Queens

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        Set<Integer> cols = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
        backtrack(board, 0, cols, diag1, diag2, result);
        return result;
    }

    private void backtrack(char[][] board, int row, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, List<List<String>> result) {
        if (row == board.length) {
            List<String> snapshot = new ArrayList<>();
            for (char[] r : board) snapshot.add(new String(r));
            result.add(snapshot);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (cols.contains(col) || d1.contains(row - col) || d2.contains(row + col)) continue;
            board[row][col] = 'Q';
            cols.add(col); d1.add(row - col); d2.add(row + col);
            backtrack(board, row + 1, cols, d1, d2, result);
            board[row][col] = '.';
            cols.remove(col); d1.remove(row - col); d2.remove(row + col);
        }
    }
}