Solving the LeetCode N‑Queens Problem

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). This problem isn't just a mental exercise; it offers a deep exploration into algorithmic logic and backtracking techniques, which 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:

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:

Solving Using Backtracking and TypeScript

This is a classic example of a problem that can be solved using a backtracking technique. In this, we create 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.

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.