51. N-Queens

LintCode 炼码

BFS解决

class Solution:
    """
    @param: n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        
        res = []
        
        def valid(present, col, new):
            for i, j in enumerate(present):
                if new==j or new==j+(col-i) or new==j-(col-i):
                    return False
            return True
        
        def generateSolution(indexList):
            solution = []
            for c in indexList:
                column = ""
                for _ in range(n):
                    if _ == c:
                        column += "Q"
                    else:
                        column += "."
                solution.append(column)
            return solution
                    
        queue = collections.deque([[_] for _ in range(n)])
        while queue:
            cur = queue.popleft()
            already = len(cur)
            if already == n:
                res.append(generateSolution(cur))
            else:
                for pos in range(n):
                    if valid(cur, already, pos):
                        queue.append(cur+[pos])
            
        return res