LeetCode 51. N-Queens

Description

https://leetcode.com/problems/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.

Example:

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

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

Explanation

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]
            result.append(row)
        
        return result
    
    
    def helper(self, n, column_index, board, board_assignment, results):
        if column_index == n:            
            results.append(self.output_result_format(board))

            return

        for i in range(0, n):
            if not self.is_valid_assignment(i, column_index, board_assignment):
                continue            
            
            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!).