· By John Kavanagh

Solving the LeetCode N‑Queens Problem

A photograph of a light-coloured chess queen in sunlight with a dark chess piece behind it.
Image by Steve Johnson, licensed from Unsplash.

The N‑Queens puzzle challenges you to place N chess queens on an NxN grid without any queen threatening another (in chess, a queen can attack any piece located on the same row, column, or diagonal). Each row adds one queen, and a conflict ends that branch of the search. That makes the puzzle a useful example of the backtracking technique I've previously covered in my problem‑solving articles.

As with any of these problems, the actual language or tech stack you use matters less than your understanding of how the algorithm works and how it can be deployed. So ‑ as always ‑ I'm going to revert to solving this in the front end, using TypeScript...


Problem Statement

Place N chess queens on an N×N chessboard so that no two queens threaten one another.

Each board configuration should be represented as a list of strings, where each string represents a row and a Q represents the placement of a queen on that row.

For Example:

Input: N = 4
Output: [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

There are only two ways a 4‑by‑4 chess board with four queens on it can be configured without the queens threatening one another:

Diagram demonstrating the two nth-queen solutions for a 4x4 grid with 4 queens. There are two solutions side-by-side.

Input: N = 1
Output: [['Q']]

If there's only one queen, and the board is only a single cell, then there's only one configuration possible:

Diagram showing the single N-Queens solution for a 1-by-1 board: one queen on its only square.

Solving Using Backtracking and TypeScript

This is a classic example of a problem that can be solved using a backtracking technique. In this, we solve the problem recursively by building a sequence of choices.

The essence of backtracking is a bit of a try‑it‑and‑see approach where we choose an option at each decision point in a systematic way. If a choice leads to a solution, we take it; otherwise, we backtrack and try the next option. In this case, the "choices" are the positions that we can place queens on the board, and the "solution" is a board where no two queens threaten each other.

So, using the backtracking algorithm, we can explore all possible board configurations and, thus, find the solutions.

In Code

Here's what that looks like using TypeScript:

const solveNQueens = (n: number): string[][] => {
  const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));
  const results: string[][] = [];

  const isSafe = (row: number, col: number) => {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < n; j++) {
        if (
          board[i][j] === 'Q' &&
          (j === col || i + j === row + col || i - j === row - col)
        ) {
          return false;
        }
      }
    }
    return true;
  };

  const backtrack = (row: number) => {
    if (row === n) {
      results.push(board.map((row) => row.join('')));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  };

  backtrack(0);
  return results;
};

How It Works

  • Initialisation:

    The board is initialised as an n x n matrix filled with dots, representing empty cells. The results array will hold our solutions.
  • Safety Check:

    The isSafe function checks if placing a queen in a particular cell is safe, that is, it doesn't threaten any other queens already placed on the board.
  • Backtracking Function:

    The backtrack function is the core of the algorithm. It tries to place a queen in each row, starting from the top. If placing the queen is safe, it makes the placement and moves on to the next row.
  • Solution Found:

    When backtrack reaches a row number equal to n, it means a solution is found. The current board configuration is converted to the required string format and added to results.
  • Backtrack:

    If placing a queen in a row is not possible without threatening another queen, the algorithm backtracks, changing the previous rows' queen positions.

The Backtracking Tree

The useful way to picture N‑Queens is as a decision tree. Each row asks one question: which column can safely hold a queen? If a placement makes the board invalid, that branch stops immediately and the algorithm returns to the previous row.

That early stopping is the point of backtracking. We are still exploring possible boards, but we avoid spending time on branches that already break the row, column or diagonal rules.


Complexity and Tests

The number of attempted placements grows quickly, and this implementation does more than check a few stored flags. Its safety helper scans every column of each earlier row, taking O(n²) time per attempted placement in the worst case. If A is the number of placements tried and Q is the number of completed boards, a useful bound for this exact code is O(A × n² + Q × n²): the second term includes converting each successful board into strings. Keeping occupied columns and diagonals in sets would change the safety‑check cost, but that is a different implementation.

The working board uses O(n²) space and the recursive calls use O(n). Keeping Q returned boards adds O(Q × n²) output space. Those are separate costs: backtracking reuses the working board, but every successful answer must survive the next undo.

Test n = 1, a small impossible board such as n = 2 or n = 3, and a known valid size such as n = 4. Those cases exercise both successful placements and branches with no solution.


Wrapping Up

And there you have it! The key to solving problems like this is in understanding how to navigate the choice tree effectively, knowing when to proceed and when to backtrack.


Untangling a delivery problem?

Send the symptoms, constraints, and affected routes. I'll help identify whether the issue sits in the application, platform, content model, deployment path, or search surface.