【LeetCode】51. N-Queens解題レポート(Python)

950 ワード

python 再帰する LeetCode LeetCodeテーマ記録

テーマ分析:
この問題は私が前に書いた八皇后問題とほぼ一致しており、出力フォーマットを変更し、その実用的な1次元配列(メタグループ)で表すことができ、例えば[.Q...]、「...Q」、「...Q...」、「...Q.」]は[1,3,0,2]と表すことができる.Pythonはメタグループ+再帰で簡単に八皇后問題を解決するこのブログはこの方法を使用しており、注釈は非常に詳細で、以下のこのコードの構想は同じで、このブログをもっと見ることができるかどうか分かりません.
テストコード:

class Solution:
    def solveNQueens(self, n):
        def check(k, j):
            for i in range(k):
                if board[i] - j == 0 or k-i == abs(board[i]-j):
                    return False
            return True
        def dfs(depth, valuelist):
            if depth==n: res.append(valuelist); return
            for i in range(n):
                if check(depth,i):
                    board[depth]=i
                    s='.'*n
                    dfs(depth+1, valuelist+[s[:i]+'Q'+s[i+1:]])
        board=[-1 for i in range(n)]
        res=[]
        dfs(0,[])
        return res

print(Solution().solveNQueens(4))	#

参考ブログ1、参考ブログ2

Installing Git HTML help

特集1-概要