Recursive backtracking algorithm for solving the "8 Queens" problem

8queens.js

const UNASSIGNED = -1;
const ASSIGNED = 1;

class Board {
  constructor(size, options) {
    this.board = [];
    this.size = size;
    this.options = options;

    for (let row = 0; row < size; row++) {
      this.board.push([]);
      for (let col = 0; col < size; col++) {
        this.board[row][col] = UNASSIGNED;
      }
    }
  }

  positionHasQueen(row, col) {
    return this.board[row][col] === ASSIGNED;
  }

  testQueenAtPosition(row, col) {
    // check for other queens to the left of position
    for (let currCol = 0; currCol < col; currCol++) {
      if (this.positionHasQueen(row, currCol)) {
        return false;
      }
    }

    // check for queens on top left diagonal of position
    for (
      let currRow = row-1, currCol = col-1;
      currRow >= 0 && currCol >= 0; 
      currRow--, currCol--
    ) {
      if (this.positionHasQueen(currRow, currCol)) {
        return false;
      }
    }

    // check for queens on bottom left diagonal of position
    for (
      let currRow = row+1, currCol = col-1;
      currRow < this.size && currCol >= 0; 
      currRow++, currCol--
    ) {
      if (this.positionHasQueen(currRow, currCol)) {
        return false;
      }
    }

    return true;
  }

  placeQueen(row, col) {
    if (this.board[row][col] === ASSIGNED) {
      throw new Error(`board: queen already exists at ${row}, ${col}`);
    }
    this.board[row][col] = ASSIGNED;

    if (this.options.debug)
      console.log(this.toString());
  }

  removeQueen(row, col) {
    if (this.board[row][col] === UNASSIGNED) {
      throw new Error(`board: no queen to remove at ${row}, ${col}`);
    }
    this.board[row][col] = UNASSIGNED;

    if (this.options.debug)
      console.log(this.toString());
  }

  toString() {
    let output = '';
    for (let row = 0; row < this.size; row++) {
      for (let col = 0; col < this.size; col++) {
        const printedPosition = this.board[row][col] === UNASSIGNED
          ? '[ ]'
          : '[Q]'
        output += printedPosition
      }
      output += '\n';
    }
    return output;
  }
}

function solve8QueensWorker(board, col) {
  if (col === board.size) {
    return true;
  }
  
  for (let row = 0; row < board.size; row++) {
    if (board.testQueenAtPosition(row, col)) {
      board.placeQueen(row, col);
      if (solve8QueensWorker(board, col+1)) return true;
      board.removeQueen(row, col); 
    }
  }
  
  return false  // tried all choices, no solution found, backtrack
}

function solve8Queens(board) {
  return solve8QueensWorker(board, 0);
}

README.md

"8 Queens Puzzle"

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queensthreaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal.

Approach

Using a recursive backtracking approach with heuristics to filter out invalid positions, we can quickly find answer to the problem.