【LeetCode with Python】 52. N-Queens II

题目

原题页面:https://oj.leetcode.com/problems/n-queens-ii/
本文地址:http://leetcode.xnerv.wang/n-queens-ii/
题目类型:Backtracking
难度评价:Hard
类似题目:(H) N-Queens

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

8-queens


分析


代码

class Solution:

    def __init__(self):
        self.paths_count = 0

    def dpTotalNQueens(self, n, prefix, level):
        for i in range(0, n):
            point = (i, level)
            is_valid = True
            for m in range(0, len(prefix)):
                if i == prefix[m]:
                    is_valid = False
                    break
                if level - m == i - prefix[m] or level - m == prefix[m] - i:
                    is_valid = False
                    break
            if is_valid:
                new_prefix = prefix[:]
                new_prefix.append(i)
                if n - 1 != level:
                    self.dpTotalNQueens(n, new_prefix, level + 1)
                else:
                    self.paths_count += 1

    # @return an integer
    def totalNQueens(self, n):
        self.dpTotalNQueens(n, [ ], 0)
        return self.paths_count

results matching ""

    No results matching ""