N-Queens hard

Problem Statement

The N-Queens problem is to place N chess queens on an NxN chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.

Example 1

Input: n = 4

Output: [ [".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."] ]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Example 2

Input: n = 1

Output: [["Q"]]

Steps

The solution uses backtracking. We'll explore possible queen placements recursively. For each row, we try placing a queen in each column. We maintain three sets to track conflicts:

1. columns: A set to keep track of columns already occupied by a queen.
2. diagonals1: A set to keep track of diagonals from top-left to bottom-right (slope = 1). The diagonal is identified by row - column.
3. diagonals2: A set to keep track of diagonals from top-right to bottom-left (slope = -1). The diagonal is identified by row + column.

If a placement doesn't result in a conflict (not in any of the three sets), we recursively explore the next row. If we successfully place queens in all rows, we add the board configuration to the result. If a placement leads to a conflict or we reach a dead end, we backtrack and try a different column.

Explanation

The backtracking algorithm systematically explores all possible queen placements. The use of sets (columns, diagonals1, diagonals2) efficiently checks for conflicts in constant time (O(1)). The recursion handles exploration of all possibilities. Once a solution is found (all queens placed without conflict), it's added to the results.

Code

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        solve(0, n, board, columns, diagonals1, diagonals2, result);
        return result;
    }

    private void solve(int row, int n, char[][] board, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2, List<List<String>> result) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] rowChars : board) {
                solution.add(new String(rowChars));
            }
            result.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            int diag1 = row - col;
            int diag2 = row + col;
            if (!columns.contains(col) && !diagonals1.contains(diag1) && !diagonals2.contains(diag2)) {
                board[row][col] = 'Q';
                columns.add(col);
                diagonals1.add(diag1);
                diagonals2.add(diag2);
                solve(row + 1, n, board, columns, diagonals1, diagonals2, result);
                diagonals2.remove(diag2);
                diagonals1.remove(diag1);
                columns.remove(col);
                board[row][col] = '.';
            }
        }
    }
}

Complexity

• Time Complexity: O(N!), where N is the size of the chessboard. In the worst case, we explore all possible permutations of queen placements.
• Space Complexity: O(N^2) to store the chessboard and auxiliary data structures (sets). The recursion depth can also be at most N.