Classical N-Queen Problem

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Classical N-Queen problem

N-Queen Problem: The Chessboard Conundrum

Imagine stepping into an interview room, and the interviewer asks you to solve the N-Queen problem. It's a modern take on the classic 8-Queen Puzzle, where you place queens on a chessboard in such a way that none can attack another. Here's a complete guide to understanding the problem and constraints.

The Basic Rules of Chessboard and Queens

First, let's get our chess terminology straight. A queen in chess can move horizontally, vertically, and diagonally. Your task is to place n queens on an n x n chessboard in such a way that none of the queens are in a position to attack each other.

Key Assumptions

Square Board: The chessboard will always be square-shaped.
Solution Exists: For n > 3, at least one non-attacking arrangement of queens exists.

Constraints to Keep in Mind

Board Size Limitations

Maximum value of n: The board can have up to 100 rows and columns.
Minimum value of n: The board must have at least 4 rows and columns.

Performance Expectations

Time Complexity: Your solution should aim to have a time complexity of O(n^2).
Space Complexity: Keep the space complexity at O(n).

Example: Solving a 4x4 Board

For a 4x4 chessboard, you could place the queens like so (Q represents a queen, and . represents an empty space):

. Q . .
. . . Q
Q . . .
. . Q .

Here, no two queens threaten each other. And voila, you've successfully solved the 4-queen problem.

Grasp these guidelines well, and you'll be several moves ahead in your coding interview.

```py
def solveNQueens(n):
    # Fill in
    pass
```
```java
public ArrayList<ArrayList<String>> solveNQueens(int n) {
    // Fill in
    return null;
}
```
```javascript
function solveNQueens(n) {
    // Fill in
}
```
```c++
vector<vector<string>> solveNQueens(int n) {
    // Fill in
    return vector<vector<string>>();
}
```
```csharp
public List<List<string>> SolveNQueens(int n) {
    // Fill in
    return null;
}
```
```go
func solveNQueens(n int) [][]string {
    // Fill in
    return nil
}
```

Feasibility determination and Proof of Concept

The N-Queens problem could stump you in an interview if you're not prepared. Let's break down how to tackle it efficiently, so you can make a smart move.

The Pitfall of Naive Brute Force

Sky-High Complexity

In an 8x8 board, the total number of possible arrangements is 8^8 = 16,777,216. That's like combing through a haystack the size of a mountain to find your needle.

No Polynomial Shortcut

Since the N-Queens problem is an NP-complete issue, no polynomial time solution is known. Brute force? Definitely a checkmate against you.

The Ace Up Your Sleeve: Backtracking

Non-Sequential Exploration

Unlike brute-force, you don't have to check every single sequential queen placement. You can place queens in a way that's much smarter.

How Backtracking is Done

Start Fresh: You begin with an empty chessboard.
First Column, First Queen: Plant a queen in the first available column of the first row.
Row Exploration: Iterate through each row, trying to find a spot where the queen can sit without being in the line of attack from any other queen.
Retreat and Reconsider: If you can't find such a spot in the current row, it's time to backtrack. Go back to the previous row and move that queen to another column.
Rinse and Repeat: Continue this process until you either find a valid arrangement of queens or have to admit defeat.

Why Backtracking Wins

Eliminates Dead-Ends

The algorithm smartly avoids going down pathways that are bound to fail, saving you precious time and computational power.

Prunes the Search Space

Because of the built-in constraint checks, you dramatically reduce the number of possible board configurations you need to explore.

Efficient & Optimal

It's like solving a puzzle where you can peek at the box cover whenever you want. You get hints that guide you to the optimal solution much faster.

8-Queen Backtracking Wikipedia

With backtracking, you're not just coding; you're strategically navigating through constraints and possibilities, turning your code into a masterstroke of problem-solving.

Board Validation Function

Before we implement the solver itself, we need to create a function that can be used to see if we can put a queen on a cell in the board. The function will take the board, a row, and a col to place into that cell of the board.

def validate_board(self, board, row, col):

public boolean validateBoard(char[][] board, int row, int col) {
}

function validateBoard(board, row, col) {
}

bool validateBoard(char** board, int row, int col) {
}

public bool ValidateBoard(char[,] board, int row, int col) {
}

func validateBoard(board [][]rune, row int, col int) bool {
}

The function will first check if there is a Queen in the same column in the board. We can check this easily by looping through the rows one at a time. Notice that we do not need to check for queens after the current row because we have not reached that point yet. Here is the python code for this validation:

# Check if row is valid
for row_it in range(row):
    if board[row_it][col] == 'Q':
        return False

// Check if row is valid
for(int row_it = 0; row_it < row; row_it++){
    if(board[row_it][col] == 'Q'){
        return false;
    }
}

// Check if row is valid
for(let row_it = 0; row_it < row; row_it++){
    if(board[row_it][col] == 'Q'){
        return false;
    }
}

// Check if row is valid
for(int row_it = 0; row_it < row; row_it++){
    if(board[row_it][col] == 'Q'){
        return false;
    }
}

// Check if row is valid
for(int row_it = 0; row_it < row; row_it++) {
    if(board[row_it, col] == 'Q') {
        return false;
    }
}

// Check if row is valid
for row_it := 0; row_it < row; row_it++ {
    if board[row_it][col] == 'Q' {
        return false
    }
}

We do not need to check for Queens in the same column because in the backtracking process, we will put only one Queen at each column.

Following this, we will check if a Queen appears in the first diagonal of the board. To do this, we will need to see how the row_it and the col_it variables in a loop increases or decreases. See the below image to understand it. The first one is for the first diagonal and the second one is for the second diagonal.

First Diagonal `row` `col` change

Second Diagonal `row` `col` change

```python
# Check if block has duplicate
row_block = row - row%3
col_block = col - col%3
for row_it in range(3):
    for col_it in range(3):
        if board[row_block+row_it][col_block+col_it] == val:
            return False

# Check if second diagonal is valid
for row_it, col_it in zip(reversed(range(row)), range(col+1, len(board))):
    if board[row_it][col_it] == 'Q':
        return False
```
```java
// Check if block has duplicate
int rowBlock = row - row % 3;
int colBlock = col - col % 3;
for (int rowIt = 0; rowIt < 3; rowIt++) {
    for (int colIt = 0; colIt < 3; colIt++) {
        if (board[rowBlock + rowIt][colBlock + colIt] == val) {
            return false;
        }
    }
}

// Check if second diagonal is valid
for (int rowIt = row - 1, colIt = col + 1; rowIt >= 0 && colIt < board.length; rowIt--, colIt++) {
    if (board[rowIt][colIt] == 'Q') {
        return false;
    }
}
```
```javascript
// Check if block has duplicate
let rowBlock = row - row % 3;
let colBlock = col - col % 3;
for (let rowIt = 0; rowIt < 3; rowIt++) {
    for (let colIt = 0; colIt < 3; colIt++) {
        if (board[rowBlock + rowIt][colBlock + colIt] === val) {
            return false;
        }
    }
}

// Check if second diagonal is valid
for (let rowIt = row - 1, colIt = col + 1; rowIt >= 0 && colIt < board.length; rowIt--, colIt++) {
    if (board[rowIt][colIt] === 'Q') {
        return false;
    }
}
```
```cpp
// Check if block has duplicate
int rowBlock = row - row % 3;
int colBlock = col - col % 3;
for (int rowIt = 0; rowIt < 3; rowIt++) {
    for (int colIt = 0; colIt < 3; colIt++) {
        if (board[rowBlock + rowIt][colBlock + colIt] == val) {
            return false;
        }
    }
}

// Check if second diagonal is valid
for (int rowIt = row - 1, colIt = col + 1; rowIt >= 0 && colIt < board.size(); rowIt--, colIt++) {
    if (board[rowIt][colIt] == 'Q') {
        return false;
    }
}
```
```csharp
// Check if block has duplicate
int rowBlock = row - row % 3;
int colBlock = col - col % 3;
for (int rowIt = 0; rowIt < 3; rowIt++) {
    for (int colIt = 0; colIt < 3; colIt++) {
        if (board[rowBlock + rowIt, colBlock + colIt] == val) {
            return false;
        }
    }
}

// Check if second diagonal is valid
for (int rowIt = row - 1, colIt = col + 1; rowIt >= 0 && colIt < board.GetLength(0); rowIt--, colIt++) {
    if (board[rowIt, colIt] == 'Q') {
        return false;
    }
}
```
```go
// Check if block has duplicate
rowBlock := row - row % 3
colBlock := col - col % 3
for rowIt := 0; rowIt < 3; rowIt++ {
    for colIt := 0; colIt < 3; colIt++ {
        if board[rowBlock+rowIt][colBlock+colIt] == val {
            return false
        }
    }
}

// Check if second diagonal is valid
for rowIt, colIt := row - 1, col + 1; rowIt >= 0 && colIt < len(board); rowIt, colIt = rowIt - 1, colIt + 1 {
    if board[rowIt][colIt] == 'Q' {
        return false
    }
}
```

Step Four

Finally if none of these return False, we are sure that a Queen at that row and col position is a valid state. So we will return true.

```python
# Everything is valid, so return True
return True
```
```java
// Everything is valid, so return true
return true;
```
```javascript
// Everything is valid, so return true
return true;
```
```cpp
// Everything is valid, so return true
return true;
```
```csharp
// Everything is valid, so return true
return true;
```
```go
// Everything is valid, so return true
return true
```

Base Conditions of Recursing Backtracking

We will start from the first element in the board. We will be putting Queens in places and then move forward. To do this, we will continuously place Queens if possible, and then increment row.

While incrementing row, we will reach at a point where row will be greater than n (out of the board). At that time, we have found a solution. So we will save a copy of the board and continue to backtrack for other solutions.

```python
if row == len(board):
    # A solution! add a copy of it
    res.append(board.copy())
    return res
```
```java
if (row == board.length) {
    // A solution! add a copy of it
    res.add(new ArrayList<>(board));
    return res;
}
```
```javascript
if (row === board.length) {
    // A solution! add a copy of it
    res.push([...board]);
    return res;
}
```
```cpp
if (row == board.size()) {
    // A solution! add a copy of it
    res.push_back(board);
    return res;
}
```
```csharp
if (row == board.Length) {
    // A solution! add a copy of it
    res.Add(new List<string>(board));
    return res;
}
```
```go
if row == len(board) {
    // A solution! add a copy of it
    res = append(res, append([]string(nil), board...))
    return res
}
```

Recursive Backtracking

For the backtracking, we will take each row and put a Queen in a feasible place (with the help of validate_board) in that row. After placing the Queen, we will recursively continue from the next row in the board.

After finishing that recursive function, we will have all the solved boards, putting a Queen at that row and col. We'll need the next step of putting current Queen in the next feasible place. That is why we will pick up the Queen (put '.' there) and continue the loop.

Finally there will be all the solutions in res. Also, we will again be at the top of the call stack in the recursive function. So we will return our desired res to the caller function.

```python
for col in range(len(board)):
    if self.validate_board(board, row, col):
        # Put a queen and move forward
        board[row] = board[row][:col] + 'Q' + board[row][col+1:]
        self.recursiveSolveNQueens(res, board, row+1)
        # Now backtrack
        board[row] = board[row][:col] + '.' + board[row][col+1:]
```
```java
for(int col = 0; col < board.length; col++) {
    if(this.validate_board(board, row, col)) {
        // Put a queen and move forward
        board[row] = board[row].substring(0, col) + "Q" + board[row].substring(col+1);
        this.recursiveSolveNQueens(res, board, row+1);
        // Now backtrack
        board[row] = board[row].substring(0, col) + "." + board[row].substring(col+1);
    }
}
```
```javascript
for(let col = 0; col < board.length; col++) {
    if(this.validate_board(board, row, col)) {
        // Put a queen and move forward
        board[row] = board[row].substr(0, col) + "Q" + board[row].substr(col+1);
        this.recursiveSolveNQueens(res, board, row+1);
        // Now backtrack
        board[row] = board[row].substr(0, col) + "." + board[row].substr(col+1);
    }
}
```
```cpp
for(int col = 0; col < board.size(); col++) {
    if(this->validate_board(board, row, col)) {
        // Put a queen and move forward
        board[row] = board[row].substr(0, col) + "Q" + board[row].substr(col+1);
        this->recursiveSolveNQueens(res, board, row+1);
        // Now backtrack
        board[row] = board[row].substr(0, col) + "." + board[row].substr(col+1);
    }
}
```
```csharp
for(int col = 0; col < board.Length; col++) {
    if(this.ValidateBoard(board, row, col)) {
        // Put a queen and move forward
        board[row] = board[row].Substring(0, col) + "Q" + board[row].Substring(col+1);
        this.RecursiveSolveNQueens(res, board, row+1);
        // Now backtrack
        board[row] = board[row].Substring(0, col) + "." + board[row].Substring(col+1);
    }
}
```
```go
for col := 0; col < len(board); col++ {
    if self.validateBoard(board, row, col) {
        // Put a queen and move forward
        board[row] = board[row][:col] + "Q" + board[row][col+1:]
        self.recursiveSolveNQueens(res, board, row+1)
        // Now backtrack
        board[row] = board[row][:col] + "." + board[row][col+1:]
    }
}
```

Start of the Backtracking Algorithm

We will start the backtracking process from row=0 and col=0. col=0 part is already taken cared by the backtracking function itself. We just need to create a board so that our recursiveSolveNQueens can start playing with the board.

To create a board, we will first create a string of size n with the python string multiplication operator '.' * n. Then we will again duplicate it n times to get the board.

```python
def solveNQueens(self, n: int) -> [[str]]:
    # For n=5, board is
    # [".....", => '.'*n
    #  ".....", => '.'*n
    #  ".....", => '.'*n
    #  ".....", => '.'*n
    #  "....."] => '.'*n
    # so, [ '.'*n ] * n
    board = ['.'*n]*n
```
```java
public List<List<String>> solveNQueens(int n) {
    // For n=5, board in Java is
    // {".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  "....."} => '.'*n
    // so, IntStream.range(0, n).mapToObj(i -> new String(new char[n]).replace('\0', '.')).collect(Collectors.toList())
    List<String> board = IntStream.range(0, n).mapToObj(i -> new String(new char[n]).replace('\0', '.')).collect(Collectors.toList());
    // Type will be replaced by actual type later
}
```
```javascript
const solveNQueens = (n) => {
    // For n=5, board in Javascript is
    // [".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  "....."] => '.'*n
    // so, [...Array(n)].map(_ => '.'.repeat(n))
    let board = [...Array(n)].map(_ => '.'.repeat(n));
    // Type will be replaced by actual type later
};
```
```cpp
std::vector<std::string> solveNQueens(int n) {
    // For n=5, board in C++ is
    // {".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  "....."} => '.'*n
    // so, std::vector<std::string> board(n, std::string(n, '.'));
    std::vector<std::string> board(n, std::string(n, '.'));
    // Type will be replaced by actual type later
}
```
```csharp
public IList<IList<string>> SolveNQueens(int n) {
    // For n=5, board in C# is
    // {".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  "....."} => '.'*n
    // so, Enumerable.Range(0, n).Select(_ => new String('.', n)).ToList()
    var board = Enumerable.Range(0, n).Select(_ => new String('.', n)).ToList();
    // Type will be replaced by actual type later
}
```
```go
func solveNQueens(n int) [][]string {
    // For n=5, board in Go is
    // {".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  ".....", => '.'*n
    //  "....."} => '.'*n
    // so, Generating a slice like this in Go is a little bit complex than other languages we need to loop through n and fill '.' n times
    board := make([]string, n)
    for i := range board {
        board[i] = strings.Repeat(".", n)
    }
    // Type will be replaced by actual type later
}
```

Complexity

Finally we will start the recursion with the board and an empty res result list. res will be the answer of our problem, so we can directly return it.

This is the most well-known algorithm for solving N-Queen problem. The time complexity is O(n^2) because we are selecting if we can put or not put a Queen at that place. The space is the board size times the result. Note that, even though it seems that the time complexity is huge, it is actually not. The maximum value of n will be only 100.

One Pager Cheat Sheet

You should design an N-Queen problem solver that can place n queens on a n x n square board in a way that no queen is in a mutual attacking position, with a minimum value of n = 4 and a maximum value of n = 100, in O(n^2) time and O(n) space complexity.
We need to use a backtracking algorithm to solve the NP-Complete 8-Queen problem due to its large search space ruling out a naive brute force solution.
A Board Validation Function is used to check if we can place a Queen in a cell of the board by looping through the rows and checking if there is a Queen in the same column, and by checking if a Queen appears in the first and second diagonals by observing the row and col variables in a loop.
We will returnTrue`if a Queen is validly placed at a givenrowandcol` position.
We will start from the first element in the board and attempt to place Queens, incrementing the row until row is greater than n, at which point a solution is found and the board is saved for further backtracking.
The algorithm will recursively evaluate row-by-row for valid positions to place the Queen and add each solution to a list of results before backtracking to the next feasible place.
We will create a board by multiplying a string of size n and duplicating it n times, then start the backtracking process at row=0 and col=0.
We will recursively select Queen positions and build up the solution list, res, with a time complexity of O(n^2) and space complexity of board size times res.

Open interactive view →