N-Queens

The n-queens puzzle is the challenge of placing n queens on an n x n chessboard so that no two queens attack each other.

Problem Statement

The n-queens puzzle is the challenge of placing n queens on an n x n chessboard so that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You can return the answer in any order.

Each solution is a board configuration, shown as an array of strings. In each string, 'Q' marks a queen, and '.' marks an empty space.

Note: No constraints or examples were shared for this problem. Feel free to send them so they can be added here.

Solution

We solve this using backtracking. We go row by row, and for each row, we try placing a queen in every column, checking each time whether that placement is safe.

Steps

• We build an empty board, filled with '.' characters.
• We use a helper function, backtrack(row):
  • If row equals n, it means we've successfully placed a queen in every row. This is one complete, valid solution, so we save a copy of the board.
  • Otherwise, we try placing a queen in every column of the current row:
    • If placing a queen at (row, col) is safe, we place it, then move on to the next row using recursion.
    • After returning from that recursive call, we remove the queen (backtrack), so we can try the next column in this row.
• We use a helper function, isSafe(row, col), to check three things before placing a queen:
  • No other queen is in the same column, in any row above the current one.
  • No other queen is on the same diagonal going up-left (checked by comparing board[row - i][col - i]).
  • No other queen is on the same diagonal going up-right (checked by comparing board[row - i][col + i]).
  • We don't need to check the same row, since we only ever place one queen per row.
• We start the process with backtrack(0), and once it's done exploring every possibility, res contains every valid solution.

Code

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    let res = [];

    const board = Array.from({ length: n }, () => Array(n).fill('.'));

    function backtrack(row) {
        if (row == n) {
            res.push(board.map(r => r.join("")));
            return;
        }

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

    function isSafe(row, col) {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false;
            }
        }

        for (let i = 1; i <= Math.min(row, col); i++) {
            if (board[row - i][col - i] === 'Q') return false;
        }

        for (let i = 1; i <= Math.min(row, n - 1 - col); i++) {
            if (board[row - i][col + i] === 'Q') return false;
        }

        return true;
    }

    backtrack(0);

    return res;
};