The Eight Queens Problem : Explanation

Eight Queens Problem Using Backtracking

The Eight Queens problem is a classic combinatorial problem. The objective is to place eight queens on an 8 × 8 chessboard so that no two queens can attack each other.

Therefore, no two queens may share:

• The same row
• The same column
• The same diagonal

How backtracking solves the problem

Backtracking builds a solution one row at a time. A queen is placed in a safe column, and the algorithm then advances to the next row. If no safe position is available, it returns to the previous row and tries another position.

If two queens occupy positions (row1, column1) and (row2, column2), they attack each other when:

column1 === column2

Math.abs(row1 - row2) === Math.abs(column1 - column2)

Select “Generate Solutions” to begin.

JavaScript backtracking algorithm

function solveQueens(row) {
  if (row === 8) {
    solutions.push([...positions]);
    return;
  }

  for (let column = 0; column < 8; column++) {
    if (isSafe(row, column)) {
      positions[row] = column;
      solveQueens(row + 1);
    }
  }
}

The Eight Queens problem has 92 solutions. The interactive demonstration above lets you inspect them individually or play them automatically.

Learn With Champak: This is an excellent example for understanding recursion, constraint checking and backtracking.