my python backtracking solution


  • 0
    A
    """
    inspired by : https://youtu.be/xouin83ebxE
    """
    
    class Solution(object):
        def solveNQueens(self, n):
            result = []
            positions = [None for i in range(n)]
            self.solve(n, 0, positions, result)
            
            return result
            
        def solve(self, n, row, positions, result):
            if n == row:
                one_result = []
                string = ''
                for pos in positions:
                    for i in range(n):
                        if pos[1] == i:
                            string += 'Q'
                        else:
                            string += '.'
                    one_result.append(string)
                    string = ''
                result.append(one_result)
                return
            
            for col in range(n):
                found_safe = True
                
                for queen in range(row):
                    if positions[queen][1] == col or \
                        positions[queen][0] - positions[queen][1] == row - col or \
                        positions[queen][0] + positions[queen][1] ==  row + col:
                                found_safe = False
                                break
                            
                if found_safe:
                    positions[row] = (row, col)
                    self.solve(n, row + 1, positions, result)
                            
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.