onenoughtone

N-Queens Pattern

What is the N-Queens Problem?

The N-Queens problem is a classic chess puzzle: place N queens on an N×N chessboard so that no two queens threaten each other.

This means no two queens can share the same row, column, or diagonal.

Backtracking Approach

The N-Queens problem is a perfect example of backtracking:

Start with an empty board
Try placing a queen in the first row, first column
Move to the next row and try placing a queen in a valid position
If no valid position exists, backtrack to the previous row and try a different position
Continue until all queens are placed or all possibilities are exhausted

Implementation

Here's how we can implement the N-Queens solution using backtracking:

Time and Space Complexity

Time Complexity:

O(N!), where N is the size of the board. In the worst case, we need to explore all possible placements of queens.

Space Complexity:

O(N²) for the board representation, plus O(N) for the recursion stack.

Previous Next

Pattern 1: N-Queens

Learn how to solve the classic N-Queens problem using backtracking.

The N-Queens Problem

The N-Queens problem is a classic chess puzzle: place N queens on an N×N chessboard so that no two queens threaten each other.

This means no two queens can share the same row, column, or diagonal.

Example for N=4:

♕

One of the two solutions for the 4-Queens problem

Why Backtracking?

The N-Queens problem is a perfect candidate for backtracking because:

Incremental Construction

We can build the solution one queen at a time, row by row.

Constraint Checking

We can easily check if placing a queen violates any constraints.

Pruning

We can abandon invalid paths early without exploring all possibilities.

Multiple Solutions

Backtracking can find all possible solutions to the problem.

Backtracking Approach

1Start Empty

Begin with an empty N×N chessboard.

2Place Queen

Try placing a queen in the first row, first valid column.

3Move Forward

Move to the next row and try placing a queen in a valid position.

4Backtrack

If no valid position exists, backtrack to the previous row and try a different position.

5Complete

Continue until all queens are placed or all possibilities are exhausted.

Implementation

Here's how we can implement the N-Queens solution using backtracking:

nQueens.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill().map(() => Array(n).fill('.'));
  
  function backtrack(row) {
    // Base case: If we've placed queens in all rows, we have a valid solution
    if (row === n) {
      // Convert the board to the required format and add to result
      const solution = board.map(row => row.join(''));
      result.push(solution);
      return;
    }
    
    // Try placing a queen in each column of the current row
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        // Place the queen
        board[row][col] = 'Q';
        
        // Recursively place queens in the next row
        backtrack(row + 1);
        
        // Backtrack: remove the queen to try other positions
        board[row][col] = '.';
      }
    }
  }
  
  function isValid(row, col) {
    // Check if there's a queen in the same column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') {
        return false;
      }
    }
    
    // Check upper-left diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') {
        return false;
      }
    }
    
    // Check upper-right diagonal
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') {
        return false;
      }
    }
    
    return true;
  }
  
  backtrack(0);
  return result;
}

Time and Space Complexity

Time Complexity

O(N!), where N is the size of the board.

In the worst case, we need to explore all possible placements of queens. For the first row, we have N options, for the second row, we have at most N-1 options, and so on.

Space Complexity

O(N²) for the board representation, plus O(N) for the recursion stack.

We need an N×N board to represent the chessboard, and the recursion stack can go up to depth N in the worst case.

Previous: Backtracking Patterns Next: Sudoku Solver Pattern

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

N-Queens Pattern

What is the N-Queens Problem?

The N-Queens problem is a classic chess puzzle: place N queens on an N×N chessboard so that no two queens threaten each other.

This means no two queens can share the same row, column, or diagonal.

Backtracking Approach

The N-Queens problem is a perfect example of backtracking:

Start with an empty board
Try placing a queen in the first row, first column
Move to the next row and try placing a queen in a valid position
If no valid position exists, backtrack to the previous row and try a different position
Continue until all queens are placed or all possibilities are exhausted

Implementation

Here's how we can implement the N-Queens solution using backtracking:

Time and Space Complexity

Time Complexity:

O(N!), where N is the size of the board. In the worst case, we need to explore all possible placements of queens.

Space Complexity:

O(N²) for the board representation, plus O(N) for the recursion stack.

Previous Next

Pattern 1: N-Queens

Learn how to solve the classic N-Queens problem using backtracking.

The N-Queens Problem

The N-Queens problem is a classic chess puzzle: place N queens on an N×N chessboard so that no two queens threaten each other.

This means no two queens can share the same row, column, or diagonal.

Example for N=4:

♕

One of the two solutions for the 4-Queens problem

Why Backtracking?

The N-Queens problem is a perfect candidate for backtracking because:

Incremental Construction

We can build the solution one queen at a time, row by row.

Constraint Checking

We can easily check if placing a queen violates any constraints.

Pruning

We can abandon invalid paths early without exploring all possibilities.

Multiple Solutions

Backtracking can find all possible solutions to the problem.

Backtracking Approach

1Start Empty

Begin with an empty N×N chessboard.

2Place Queen

Try placing a queen in the first row, first valid column.

3Move Forward

Move to the next row and try placing a queen in a valid position.

4Backtrack

If no valid position exists, backtrack to the previous row and try a different position.

5Complete

Continue until all queens are placed or all possibilities are exhausted.

Implementation

Here's how we can implement the N-Queens solution using backtracking:

nQueens.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill().map(() => Array(n).fill('.'));
  
  function backtrack(row) {
    // Base case: If we've placed queens in all rows, we have a valid solution
    if (row === n) {
      // Convert the board to the required format and add to result
      const solution = board.map(row => row.join(''));
      result.push(solution);
      return;
    }
    
    // Try placing a queen in each column of the current row
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        // Place the queen
        board[row][col] = 'Q';
        
        // Recursively place queens in the next row
        backtrack(row + 1);
        
        // Backtrack: remove the queen to try other positions
        board[row][col] = '.';
      }
    }
  }
  
  function isValid(row, col) {
    // Check if there's a queen in the same column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') {
        return false;
      }
    }
    
    // Check upper-left diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') {
        return false;
      }
    }
    
    // Check upper-right diagonal
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') {
        return false;
      }
    }
    
    return true;
  }
  
  backtrack(0);
  return result;
}

Time and Space Complexity

Time Complexity

O(N!), where N is the size of the board.

In the worst case, we need to explore all possible placements of queens. For the first row, we have N options, for the second row, we have at most N-1 options, and so on.

Space Complexity

O(N²) for the board representation, plus O(N) for the recursion stack.

We need an N×N board to represent the chessboard, and the recursion stack can go up to depth N in the worst case.

Previous: Backtracking Patterns Next: Sudoku Solver Pattern