LeetCode 51. N-Queens



The n-queens puzzle is the problem of placing n queens on an n×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.


Input: 4
Output: [
 [".Q..",  // Solution 1

 ["..Q.",  // Solution 2
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.


start from each column do backtracking

Python Solution

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        results = []
        board_assignment = {
            'rows': {},
            'columns': {},
            'sum': {},
            'diff': {}                        
        board = [["." for j in range(0, n)] for i in range(0, n)]
        self.helper(n, 0, board, board_assignment, results)
        return results
    def output_result_format(self, board):
        result = []
        for i in range(0, len(board)):
            row = ""
            for j in range(0, len(board[0])):
                row += board[i][j]
        return result
    def helper(self, n, column_index, board, board_assignment, results):
        if column_index == n:            


        for i in range(0, n):
            if not self.is_valid_assignment(i, column_index, board_assignment):
            board[i][column_index] = "Q"
            board_assignment['rows'][i] = True
            board_assignment['columns'][column_index] = True
            board_assignment['diff'][(i - column_index)] = True            
            board_assignment['sum'][(i + column_index)] = True            
            self.helper(n, column_index + 1, board, board_assignment, results)
            board[i][column_index] = "."
            del board_assignment['rows'][i]
            del board_assignment['columns'][column_index]   
            del board_assignment['diff'][(i - column_index)]                   
            del board_assignment['sum'][(i + column_index)]                   

    def is_valid_assignment(self, row_index, column_index, board_assignment):
        if row_index in board_assignment['rows']:
            return False
        if column_index in board_assignment['columns']:
            return False

        if (row_index - column_index) in board_assignment['diff']:
            return False
        if (row_index + column_index) in board_assignment['sum']:
            return False
        return True    
  • Time complexity: O(N!).
  • Space complexity: O(N!).

Leave a Reply

Your email address will not be published. Required fields are marked *