N-Queens Problem Backtracking Approach in JavaScript: A Complete Implementation Guide

The N-Queens problem backtracking approach uses a depth-first recursive algorithm that places queens row by row, validates safety against existing queens, and backtracks when conflicts occur to explore all valid board configurations.

The N-Queens puzzle is a classic constraint satisfaction problem implemented in the trekhleb/javascript-algorithms repository. This article examines the backtracking implementation located in src/algorithms/uncategorized/n-queens/nQueens.js, breaking down how the algorithm efficiently searches the solution space while pruning invalid branches early.

Understanding the N-Queens Backtracking Algorithm

The backtracking approach treats the N-Queens problem as a depth-first search through a state space tree. Each level of the tree represents a row on the chessboard, and each branch represents placing a queen in a specific column of that row.

Board Representation and Data Structures

Rather than using a two-dimensional array, the implementation optimizes memory with a one-dimensional array called queensPositions of length N. Each index represents a row, and the value stored is either:

• null — indicating no queen placed in that row
• A QueenPosition instance — containing rowIndex, columnIndex, and pre-computed diagonal identifiers

This representation enables O(1) access to check if a row contains a queen and simplifies the backtracking step.

The Safety Check Mechanism

Before placing a queen, the algorithm validates the position using the isSafe function. This function iterates through all previously placed queens (stored in queensPositions) and verifies that the candidate position does not share:

• The same column
• The same row (implicitly handled by the array structure)
• Either diagonal (both positive and negative slopes)

The diagonal checks use pre-computed identifiers stored in the QueenPosition objects, avoiding redundant calculations during the safety validation.

Core Implementation in nQueens.js

The backtracking logic resides in the nQueensRecursive function, which implements the recursive depth-first search with explicit backtracking.

The Recursive Backtracking Function

The recursive function accepts the current state: the solutions array, the queensPositions board state, the total queensCount (N), and the current rowIndex being processed.

For each row, the algorithm iterates through every column (0 to N-1). When isSafe returns true, the code:

1. Creates a new QueenPosition instance for the current row and column
2. Stores it in queensPositions[rowIndex]
3. Recursively calls nQueensRecursive with rowIndex + 1

When rowIndex equals queensCount, the algorithm has successfully placed N queens. It clones the current queensPositions array and pushes it to the solutions array.

The Backtracking Step

The critical backtracking mechanism occurs after the recursive call returns. Regardless of whether the deeper recursion found solutions or hit dead ends, the algorithm executes:

queensPositions[rowIndex] = null;

This null assignment removes the queen from the current row, restoring the board to its state before the trial placement. The loop then continues to the next column, systematically exploring all possible configurations without maintaining state pollution between branches.

Helper Classes and Utilities

QueenPosition Class

Located in src/algorithms/uncategorized/n-queens/QueenPosition.js, this utility class encapsulates position logic and pre-computes values for efficient conflict detection.

The constructor accepts rowIndex and columnIndex, then calculates:

• leftDiagonal — rowIndex - columnIndex (identifies the negative-slope diagonal)
• rightDiagonal — rowIndex + columnIndex (identifies the positive-slope diagonal)

These identifiers allow the isSafe function to check diagonal conflicts using simple integer comparisons rather than calculating slopes during each safety check.

Practical Usage Examples

The public nQueens function serves as the entry point. It initializes the board state and launches the recursive solver:

import nQueens from './src/algorithms/uncategorized/n-queens/nQueens.js';

// Solve for 4 queens (2 solutions exist)
const solutionsForFour = nQueens(4);
console.log(`Found ${solutionsForFour.length} solutions for 4 queens`);
console.log('First solution coordinates:', 
  solutionsForFour[0].map(q => [q.rowIndex, q.columnIndex])
);

// Solve the classic 8-queens problem (92 solutions)
const solutionsForEight = nQueens(8);
console.log(`Total solutions for 8 queens: ${solutionsForEight.length}`);

Each solution returned is an array of QueenPosition instances representing one valid board configuration. You can transform these into visual representations:

// Convert solution to chessboard visualization
function visualizeSolution(solution, n) {
  const board = Array(n).fill().map(() => Array(n).fill('.'));
  solution.forEach(({ rowIndex, columnIndex }) => {
    board[rowIndex][columnIndex] = 'Q';
  });
  return board.map(row => row.join(' ')).join('\n');
}

Time Complexity and Performance

The N-Queens problem backtracking approach has a worst-case time complexity of O(N!) because it explores permutations of row placements. However, the aggressive pruning via the isSafe checks significantly reduces the actual search space compared to a brute-force enumeration of all N^N possibilities.

The space complexity is O(N) for the recursion stack and the queensPositions array, making it memory-efficient even for larger board sizes up to N ≈ 15.

For production use requiring larger N values, the repository also provides nQueensBitwise.js, which implements a bitwise optimization of the same backtracking algorithm for improved constant factors.

Summary

• The N-Queens backtracking implementation resides in src/algorithms/uncategorized/n-queens/nQueens.js and uses depth-first search with explicit state restoration.
• The board state is tracked using a one-dimensional queensPositions array where indices represent rows and values store QueenPosition objects or null.
• The isSafe function validates placements against columns and both diagonals using pre-computed identifiers from the QueenPosition class.
• Backtracking occurs by setting queensPositions[rowIndex] = null after recursive calls return, enabling exploration of alternative branches without state pollution.
• The algorithm runs in O(N!) time with O(N) space complexity, suitable for N ≤ 15, with a bitwise-optimized variant available for performance-critical applications.

Frequently Asked Questions

How does the backtracking algorithm know when it has found a valid solution?

The algorithm detects a complete solution when the rowIndex parameter equals queensCount (the board size N). At this point, the function clones the current queensPositions array and pushes it to the solutions array before returning to explore other branches. This check occurs before attempting to place queens in a non-existent row.

What is the purpose of the QueenPosition class in the N-Queens implementation?

The QueenPosition class encapsulates coordinate data and pre-computes diagonal identifiers to optimize conflict detection. It stores rowIndex, columnIndex, leftDiagonal (row - column), and rightDiagonal (row + column). These pre-calculated values allow the isSafe function to check diagonal conflicts using simple integer comparisons rather than recalculating slopes during each validation.

Why does the algorithm use a one-dimensional array instead of a 2D matrix?

The one-dimensional queensPositions array provides both memory efficiency and algorithmic simplicity. Since the N-Queens rules prohibit two queens from sharing the same row, each row can contain at most one queen. Therefore, the array index represents the row, and the value at that index represents the column (or null if empty). This reduces space complexity to O(N) and eliminates the need to track row conflicts explicitly.

How does the bitwise optimization in nQueensBitwise.js differ from the standard backtracking approach?

The nQueensBitwise.js implementation replaces the isSafe checks and QueenPosition objects with bitwise operations on integer bitmasks. It uses three bitmasks to track occupied columns and diagonals, allowing safety checks and placement updates to occur in constant time using bitwise AND, OR, and shift operations. While the asymptotic complexity remains O(N!), the reduced constant factors make it significantly faster for larger N values compared to the array-based approach.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}