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

> Learn the N-Queens problem backtracking approach in JavaScript. This guide details the recursive algorithm, safe queen placement, and conflict resolution for finding all solutions.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: how-to-guide
- Published: 2026-02-24

---

**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](https://github.com/trekhleb/javascript-algorithms) repository. This article examines the backtracking implementation located in [`src/algorithms/uncategorized/n-queens/nQueens.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/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:

```javascript
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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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:

```javascript
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:

```javascript
// 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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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.