[leetcode]N-Queens @ Python

原題住所:https://oj.leetcode.com/problems/n-queens/
标题:定番のN皇后問題.
解題構想:このタイプの問題を総称して再帰的遡及問題と呼び,決定ツリーに対する深さ優先探索(dfs)とも呼ぶことができる.N皇后問題のテクニックの鍵は碁盤の表現方法にあり,ここでは配列を1つ使えば表現できる.例えばboard=[1,3,0,2]、これは4皇后問題の1つの解で、意味は:0行目で、皇后は1列目に置く;1行目で、皇后は3列目に置かれた.2行目では、皇后は0列目に置かれています.3行目で、皇后は2列目に置かれています.この問題は再帰解法を提供し,次の問題は非再帰を用いる.check関数は、k行目、j列目に配置できるかどうかを確認するために使用されます.
コード:

class Solution:
    # @return a list of lists of string
    def solveNQueens(self, n):
        def check(k, j):  # check if the kth queen can be put in column j!
            for i in range(k):
                if board[i]==j or abs(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