N-Queens

Java

class Solution {
    private Set<Integer> vertical;
    private Set<Integer> cross1;
    private Set<Integer> cross2;
    List<List<String>> result;
    
    public List<List<String>> solveNQueens(int n) {
        result = new ArrayList<>();
        vertical = new HashSet<>();
        cross1 = new HashSet<>();
        cross2 = new HashSet<>();
        
        helper(n, 0, new ArrayList<>());
        
        return result;
    }
    
    private void helper(int n, int row, List<Integer> path) {
        if (row == n) {
            result.add(convert(path));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            int cross1Val = row + col;
            int cross2Val = row - col;
            if (notValid(col, cross1Val, cross2Val)) {
                continue;
            }
            vertical.add(col);
            cross1.add(cross1Val);
            cross2.add(cross2Val);
            path.add(col);
            
            helper(n, row + 1, path);
            
            vertical.remove(col);
            cross1.remove(cross1Val);
            cross2.remove(cross2Val);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean notValid(int col, int cross1Val, int cross2Val) {
        return vertical.contains(col) || cross1.contains(cross1Val) || cross2.contains(cross2Val);
    }
    
    private List<String> convert(List<Integer> path) {
        char[] board = new char[path.size()];
        Arrays.fill(board, '.');

        return path.stream()
            .map(val -> {
                board[val] = 'Q';
                String newBoard = new String(board);
                board[val] = '.';
                return newBoard;
            })
            .collect(Collectors.toList());
    }
}