LietCode
N-Queens Problem

N-Queens Problem

Abhi's photo
Abhi
·

4 min read

1) Describe the Question with Example

Question: Place 4 queens on a 4x4 chessboard so that no two queens threaten each other. This means:

  • No two queens share the same row.

  • No two queens share the same column.

  • No two queens share the same diagonal.

Example:

A solution to the 4-Queens problem could look like this:

[
  [".", "Q", ".", "."],
  [".", ".", ".", "Q"],
  ["Q", ".", ".", "."],
  [".", ".", "Q", "."]
]

Here, each "Q" represents a queen and "." represents an empty cell. No two queens can attack each other.

2) Short Easy to Remember Solution/Approach

  1. Place queens one by one in different rows.

  2. Check if placing a queen in a column is safe.

  3. If safe, place the queen and move to the next row.

  4. If placing the queen leads to a conflict, remove it (backtrack) and try the next column.

  5. Repeat until all queens are placed or all possibilities are tried.

3) Solution in JavaScript with Code Commenting

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

    // Check if it's safe to place a queen at board[row][col]
    function isSafe(board, row, col) {
        // Check the column
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }

        // Check the diagonal (top-left to bottom-right)
        for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }

        // Check the diagonal (top-right to bottom-left)
        for (let i = row, j = col; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }

        return true;
    }

    // Try to place queens row by row
    function backtrack(board, row) {
        if (row === n) {
            const copy = board.map(r => r.join(''));
            solutions.push(copy);
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q'; // Place queen
                backtrack(board, row + 1); // Move to next row
                board[row][col] = '.'; // Remove queen (backtrack)
            }
        }
    }

    backtrack(board, 0); // Start from the first row
    return solutions;
}

const solutions = solveNQueens(4);
console.log(solutions);

4) Explanation of the Solution in an Easy-to-Understand Way with a Real-Life Example

Imagine you have a small 4x4 grid and 4 toy queens. You need to place these toy queens on the grid so that none of them can "see" each other, like playing a hide-and-seek game.

  1. You start by placing the first queen in the first row.

  2. Then, you move to the next row and try placing the second queen in each column, checking if it's safe.

  3. If placing the second queen is safe (not in the same column or diagonal as the first queen), you place it and move to the third row.

  4. If it's not safe, you move the second queen to the next column and check again.

  5. If you can't place a queen in any column of a row, you go back (backtrack) and move the previous queen to the next column and try again.

  6. You repeat this process until all queens are placed safely on the board.

5) Code Explanation in Pointers

  • isSafe Function:

    • Checks if placing a queen at a specific position is safe.

    • Looks for any queen in the same column or diagonals.

  • backtrack Function:

    • Tries to place queens row by row.

    • If all queens are placed (row === n), it adds the current board configuration to the solutions.

    • For each column, it checks if placing a queen is safe and if so, places the queen and moves to the next row.

    • If placing the queen leads to a conflict, it removes the queen (backtracks) and tries the next column.

6) Complexities

  • Time Complexity: (O(n!))

    • This is because for each row, we try all columns, and for each placement, we check all possible configurations recursively.

  • Space Complexity: (O(n^2))

    • This is for storing the board and recursive call stack space.

Would you like to try another easy problem or have any questions about this one?

backtracking