Mastering the N-Queens Problem with Backtracking in JavaScript

11.3.3 N-Queens Problem

The N-Queens problem is a classic example in the study of algorithms and data structures, often used to illustrate the power of backtracking. It involves placing N queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal. The problem is not only a fascinating puzzle but also a great way to understand recursive algorithms and constraint satisfaction problems.

Understanding the N-Queens Problem

The challenge of the N-Queens problem lies in its constraints. Each queen must be placed such that it does not share a row, column, or diagonal with another queen. This makes the problem exponentially complex as N increases, due to the factorial growth of possible configurations.

Problem Constraints

1. Rows and Columns: Each row and column can contain only one queen.
2. Diagonals: No two queens can be on the same diagonal. This includes both the main diagonals (top-left to bottom-right) and the anti-diagonals (top-right to bottom-left).

Backtracking Approach

Backtracking is a systematic way to iterate through all possible configurations of a search space. It involves placing queens one by one in different rows, starting from the topmost row. For each row, the algorithm tries all columns and checks if placing a queen in a particular column is safe. If it is safe, the algorithm proceeds to place queens in the subsequent rows. If placing a queen leads to a situation where no further queens can be placed, the algorithm backtracks and tries the next possible position.

Steps in the Backtracking Algorithm

1. Place Queens Row by Row: Start from the first row and attempt to place a queen in each column.
2. Check for Conflicts: Before placing a queen, check if the position is safe using the isSafe function.
3. Backtrack if Necessary: If a queen placement leads to no valid positions in subsequent rows, remove the queen (backtrack) and try the next column.
4. Repeat: Continue this process until all queens are placed or all possibilities are exhausted.

Implementing the N-Queens Solution in JavaScript

Let’s dive into the implementation of the N-Queens problem using JavaScript. The solution involves a recursive function that attempts to place queens on the board.

function solveNQueens(n) {
  const solutions = [];
  const board = new Array(n).fill(0).map(() => new Array(n).fill('.'));
  placeQueen(board, 0, solutions);
  return solutions;
}

function placeQueen(board, row, solutions) {
  if (row === board.length) {
    solutions.push(board.map(r => r.join('')));
    return;
  }
  for (let col = 0; col < board.length; col++) {
    if (isSafe(board, row, col)) {
      board[row][col] = 'Q';
      placeQueen(board, row + 1, solutions);
      board[row][col] = '.'; // Backtrack
    }
  }
}

function isSafe(board, row, col) {
  // Check column
  for (let i = 0; i < row; i++) {
    if (board[i][col] === 'Q') return false;
  }
  // Check diagonal (upper left)
  for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 'Q') return false;
  }
  // Check diagonal (upper right)
  for (let i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
    if (board[i][j] === 'Q') return false;
  }
  return true;
}

Explanation of the Code

• solveNQueens(n): Initializes the board and calls the recursive function placeQueen.
• placeQueen(board, row, solutions): Attempts to place a queen in each column of the given row. If a queen is placed successfully in the last row, the current board configuration is added to the solutions.
• isSafe(board, row, col): Checks if placing a queen at board[row][col] is safe by ensuring no other queens are in the same column or diagonals.

Analyzing the Algorithm’s Complexity

The time complexity of the N-Queens problem is approximately O(N!), where N is the number of queens. This is due to the factorial nature of permutations involved in trying different configurations. The space complexity is O(N^2) due to the storage required for the board.

Optimization Techniques

1. Use Arrays for Tracking: Instead of checking the entire board for conflicts, use arrays to track occupied columns and diagonals. This reduces the number of checks needed.
2. Pruning: Implement early termination in the isSafe function to stop checking as soon as a conflict is found.

Examples and Solutions

For small values of N, such as 4 or 5, the solutions can be easily visualized. For instance, the 4-Queens problem has two distinct solutions, which can be represented as:

Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .

Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

Encouragement to Experiment

Experimenting with different board sizes can provide deeper insights into the problem’s complexity. Try implementing additional optimizations or visualizing the board to better understand the backtracking process.

Conclusion

The N-Queens problem is an excellent exercise in understanding backtracking and constraint satisfaction. By implementing a solution in JavaScript, you can gain valuable insights into recursive algorithms and optimization techniques. This problem not only enhances your problem-solving skills but also prepares you for tackling more complex algorithmic challenges.

Quiz Time!