Skip to content

Instantly share code, notes, and snippets.

@mbchoa
Last active July 26, 2020 00:27
Show Gist options
  • Save mbchoa/04d1fbd431ea4c4535915d0d030f628a to your computer and use it in GitHub Desktop.
Save mbchoa/04d1fbd431ea4c4535915d0d030f628a to your computer and use it in GitHub Desktop.
Recursive backtracking algorithm for solving the "8 Queens" problem
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);
}

"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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment