> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/hard/51.-n-queens.md).

# 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;
}

```