首页 > 代码库 > LeetCode N-Queens II

LeetCode N-Queens II

LeetCode解题之N-Queens II


原题

在N-Queens的基础上计算出共同拥有多少种不同的解法。

技术分享

注意点:

  • 仅仅须要计数

样例:

输入: n = 8

输出: 92

解题思路

思路与 N-Queens 一样。只是把原先用来最后拼装的參数之类都去掉了。换了一个计数器来记录数量。

AC源代码

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.col = [False] * n
        self.diag = [False] * (2 * n)
        self.anti_diag = [False] * (2 * n)
        self.result = 0
        self.recursive(0, n)
        return self.result

    def recursive(self, row, n):

        if row == n:
            self.result += 1
        else:
            for i in range(n):
                if not self.col[i] and not self.diag[row + i] and not self.anti_diag[n - i + row]:
                    self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = True
                    self.recursive(row + 1, n)
                    self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = False


if __name__ == "__main__":
    assert Solution().totalNQueens(8) == 92

欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

LeetCode N-Queens II