Crack the Backend

Problem Statement

Place n queens on an n×n chessboard such that no two queens attack each other. A queen can attack any piece in the same row, column, or diagonal. Return all distinct solutions; each solution is a board configuration where 'Q' and '.' represent a queen and an empty cell. Return format: list of lists of strings (each string is a row).

We place one queen per row. For row r, we try each column c; we need to check that c is not already used and that the two diagonals (row-col and row+col) are not already used. We can keep sets for columns and diagonals to check in O(1).

Key Observations

Backtracking by row: dfs(row): if row == n, we have placed n queens — add the current board to the result (convert to the required string list format). Otherwise, for each column c: if (c not in cols and row-c not in diag1 and row+c not in diag2), place the queen (add to sets, set board[row][c]='Q'), recurse dfs(row+1), then remove the queen (backtrack).
Two diagonals: one has constant row - col, the other row + col. Tracking these avoids checking all previous queens.

Approach

High-level: Place queens row by row. For row row, try each column c; if no conflict with previously placed queens (same column, or same diagonal row±col), place queen, recurse row+1, remove queen. When row==n, record the board.

Steps: Maintain cols, diag1 (row-col), diag2 (row+col) sets. dfs(row): if row==n add board and return. For c=0..n-1: if c not in cols and (row-c) not in diag1 and (row+c) not in diag2, add to sets, board[row][c]='Q', dfs(row+1), remove from sets and board.

Implementation

Java

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    int[] cols = new int[n];
    dfs(n, 0, cols, result);
    return result;
}

void dfs(int n, int row, int[] cols, List<List<String>> result) {

    if (row == n) { result.add(toBoard(cols)); return; }
    for (int c = 0; c < n; c++) {
        if (valid(cols, row, c)) {
            cols[row] = c;
            dfs(n, row + 1, cols, result);
        }
    }
}

boolean valid(int[] cols, int row, int c) {

    for (int r = 0; r < row; r++)
    if (cols[r] == c || row - r == Math.abs(c - cols[r])) {
        return false;
    }

    return true;
}

Test Cases

Example 1

Input

n = 4

Expected

2 solutions

Explanation

Two distinct board configurations.

Complexity Analysis

Time: O(n!).
Space: O(n).

Follow-ups

N-Queens II: return only the count of solutions.