We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

N-Queens

Difficulty: Hard

Problem Description

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Key Insights

  • The problem can be solved using backtracking, a common technique for constraint satisfaction problems.
  • Each queen must be placed in such a way that it does not threaten others, meaning no two queens can share the same row, column, or diagonal.
  • The board can be represented as a list of strings, where each string represents a row of the board.
  • The solution requires exploring all possible configurations while pruning invalid placements.

Space and Time Complexity

Time Complexity: O(n!), where n is the number of queens (or the size of the board). This is because we may explore every possible arrangement of queens. Space Complexity: O(n), as we store the state of the board and the positions of the queens during the backtracking process.

Solution

The solution uses a backtracking approach to explore all possible placements of queens on the board. We maintain lists to track the columns and diagonals that are already attacked by queens. For each row, we attempt to place a queen in every column, checking if it is valid (i.e., not under attack). If valid, we place the queen and move to the next row. If we reach the last row, a valid configuration is found and added to the results. We backtrack by removing the queen and trying the next column.

Code Solutions

def solveNQueens(n):
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row] = '.' * col + 'Q' + '.' * (n - col - 1)
            backtrack(row + 1, cols, diag1, diag2, board)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    result = []
    backtrack(0, set(), set(), set(), ['.' * n] * n)
    return result
← Back to All Questions