An intuitive solution in Python


  • 0
    L

    The idea is that

    1. To put n queens in a n by n board, each row should have and can only have exactly one queen. Thus a 4x4 board with 4 queens can be represented as [a, b, c, d], abcd here indicate index of the queen in each row.
    2. The queen in the new row cannot be in the same column with existing queens, thus d cannot be the same value of a, b, c in the case above.
    3. The queen in the new row cannot be diagonal to other existing queens. This can be expressed as 3 + d != 2 + a and 3 - d != 2 - a.
    class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            results = []
            stack = [([], set(), set())]
    
            while stack:
                queens, diff, sums = stack.pop()
                if len(queens) == n:
                    results.append(queens)
                    continue
                for q in range(n):
                    minus = len(queens) - q
                    add = len(queens) + q
                    if q in queens or minus in diff or add in sums:
                        continue
                    stack.append((queens + [q], diff | set([minus]), sums | set([add])))
    
            return [['.' * q + 'Q' + '.' * (n - q - 1) for q in queens] for queens in results]
    

Log in to reply
 

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