Jianbo Dai's

lc051.N皇后

 
  • Mar 17, 2021

题目链接

啊经典的N皇后问题，套用了一下自己总结的回溯的模板，就做掉了，还行。这个算法的时间复杂度是O(N!)，空间复杂度是O（N）。

python:

import copy

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        def isConfict(x, y, others):
            if y in others:
                return False
            for i, j in enumerate(others):
                if x - i == y - j or x - i == - (y - j):
                    return False
            return True

        def backtrack(row, path):
            if row == n:
                res = []
                for pos in path:
                    line = ["." for _ in range(n)]
                    line[pos] = "Q"
                    res.append("".join(line))
                results.append(res)
            for col in range(n):
                if isConfict(row, col, path):
                    path.append(col)
                    backtrack(row + 1, path)
                    path.pop()

        results = []
        backtrack(0, [])
        return results
Search