# 51. N-Queens

## Intuition

We need to place `n` queens such that none of them attack each other. A queen can attack any other queen in the same row, column, or diagonal. We solve this using **backtracking** — trying all possible placements row-by-row and undoing invalid ones. If we reach the last row with valid placements, we record the solution.

## Complexity

| Space Complexity  | Time Complexity  |
| ----------------- | ---------------- |
| $$\text{O}(N^2)$$ | $$\text{O}(N!)$$ |

## Code

```java
List<List<String>> allValidArrangements = new LinkedList<>();

// Check if a queen can be placed at (row, col)
public boolean isSafe(boolean[][] board, int row, int col, int n) {
    // Check the column
    for (int i = 0; i < n; ++i) {
        if (board[i][col]) return false;
    }

    // Check top-left diagonal
    for (int i = col - 1, j = row - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[j][i]) return false;
    }

    // Check bottom-right diagonal
    for (int i = col + 1, j = row + 1; i < n && j < n; ++i, ++j) {
        if (board[j][i]) return false;
    }

    // Check top-right diagonal
    for (int i = col + 1, j = row - 1; i < n && j >= 0; ++i, --j) {
        if (board[j][i]) return false;
    }

    // Check bottom-left diagonal
    for (int i = col - 1, j = row + 1; i >= 0 && j < n; --i, ++j) {
        if (board[j][i]) return false;
    }

    return true;
}

// Backtracking function to place queens row-by-row
public void solveQueens(boolean[][] board, int currentRow, int n) {
    // All queens placed successfully
    if (currentRow == n) {
        List<String> currentBoard = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            StringBuilder rowRepresentation = new StringBuilder();
            for (int j = 0; j < n; ++j) {
                rowRepresentation.append(board[i][j] ? "Q" : ".");
            }
            currentBoard.add(rowRepresentation.toString());
        }
        allValidArrangements.add(currentBoard);
        return;
    }

    // Try placing a queen in each column of the current row
    for (int col = 0; col < n; ++col) {
        if (isSafe(board, currentRow, col, n)) {
            board[currentRow][col] = true;
            solveQueens(board, currentRow + 1, n);
            board[currentRow][col] = false; // Backtrack
        }
    }
}

// Entry function
public List<List<String>> solveNQueens(int n) {
    boolean[][] board = new boolean[n][n];
    solveQueens(board, 0, n);
    return allValidArrangements;
}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://private-26.gitbook.io/notes/coding/hard/51.-n-queens.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.