N-Queens Algorithm in JavaScript: Solve the Classic Chess Puzzle with Backtrackin

N-Queens Algorithm

The N-Queens problem is a classic chess-based puzzle where the goal is to place N queens on an N × N chessboard so that no two queens threaten each other. A queen can attack in any direction: horizontally, vertically, or diagonally.

🧠 Understanding the Problem

To solve this problem, we must ensure that no two queens share:

• The same row
• The same column
• The same diagonal (both main and anti-diagonal)

This problem is typically solved using the Backtracking algorithm, which tries different placements and backtracks when an invalid state is found.

⚙️ Implementation in JavaScript

Below is an efficient JavaScript implementation using the backtracking approach:

  
class NQueens {
  constructor(size) {
    if (size < 0) {
      throw RangeError('Invalid board size')
    }
    this.board = new Array(size).fill('.').map(() => new Array(size).fill('.'))
    this.size = size
    this.solutionCount = 0
  }

  isValid([row, col]) {
    // Check left of current row
    for (let i = 0; i < col; i++) {
      if (this.board[row][i] === 'Q') return false
    }

    // Check upper left diagonal
    for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
      if (this.board[i][j] === 'Q') return false
    }

    // Check lower left diagonal
    for (let i = row, j = col; j >= 0 && i < this.size; i++, j--) {
      if (this.board[i][j] === 'Q') return false
    }

    return true
  }

  placeQueen(row, col) {
    this.board[row][col] = 'Q'
  }

  removeQueen(row, col) {
    this.board[row][col] = '.'
  }

  solve(col = 0) {
    if (col >= this.size) {
      this.solutionCount++
      return true
    }

    for (let i = 0; i < this.size; i++) {
      if (this.isValid([i, col])) {
        this.placeQueen(i, col)
        this.solve(col + 1)
        this.removeQueen(i, col)
      }
    }

    return false
  }

  printBoard(output = (value) => console.log(value)) {
    if (!output._isMockFunction) {
      output('\n')
    }
    for (const row of this.board) {
      output(row)
    }
  }
}

export { NQueens }
  
  

🚀 How the Algorithm Works

1️⃣ Start with an empty board of size N × N.
2️⃣ Try placing a queen in the first available row of an empty column.
3️⃣ If the placement is valid (no conflicts), move to the next column.
4️⃣ If no valid position is found, backtrack to the previous column and try the next possibility.
5️⃣ Repeat until all queens are placed successfully or no solution is possible.

🛠️ Time Complexity

The worst-case time complexity of this approach is O(N!) because it explores every possible arrangement of queens on the board.

✅ Example Output

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

🎯 Applications

• Solving complex combinatorial puzzles
• AI and robotics for constraint satisfaction problems
• Optimizing path-finding algorithms

📌 Conclusion

The N-Queens problem is an excellent demonstration of backtracking, showcasing how recursion and constraint validation work together. Understanding this algorithm will help you tackle more advanced backtracking problems.