Backtracing Python Solution, very self-explained


  • 0
    M
    class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            
            solutions=[]
            # generate the solution in list format
            self.helper(n,solutions,[])
            
            ret=[]
            
            # draw the board
            for sltn in solutions:
                board=[]
                for s in sltn:
                    board_row=""
                    for i in range(n):
                        if s==i:
                            board_row+='Q'
                        else:
                            board_row+='.'
                    board.append(board_row[:])
                ret.append(board[:])
            
            return ret
            
        def helper(self,n,solutions,solution):
            if self.cnflct(solution)==True:
                # test if there is a conflict
                return
            else:
                if len(solution)==n:
                    solutions.append(solution[:])
    
                
            for i in range(n):
                # place a queen
                solution.append(i)
                self.helper(n,solutions,solution)
                solution.pop()
            
        def cnflct(self,solution):
            if len(solution)==1 or len(solution)==0:
                return False
            else:
                r=len(solution)-1
                c=solution[r]
                for i in range(len(solution)-1):
                    # conflict if only two queens are on the same row/column/diagonal line
                    if i==r or solution[i]==c or solution[i]+i==c+r or solution[i]-i==c-r:
                        return True
            return False
    

Log in to reply
 

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