遞歸法

• 用一個一維N元數(shù)組來存放每一行皇后的位置，這樣就不存在行沖突了，只要判斷哪一列可以放置就可以了，如果找到一個可以放置皇后的位置j后，則會遞歸探測下一行，結束后則會繼續(xù)探測i行j+1列，故可以找到所有的N皇后的解。

class Solution:
    #最后mark數(shù)組里面標記的是皇后的位置，例如mark[0] = 2, 表示第一行皇后放在第3列的位置
    def make(self, mark):
        #初始化數(shù)組
        r = [['.' for _ in range(len(mark))] for _ in range(len(mark))]
        #將每一行中皇后的位置用‘Q’代替
        for i in mark:
            r[i][mark[i]] = 'Q'
        #枚舉，將原來散的元素連接成字符串
        for k, v in enumerate(r):
            r[k] = ''.join(v)
        return r

    #遞歸函數(shù)，核心
    def recursive(self, mark, cur, ret):

        #如果當前行是最后一行，記錄一個解，并返回上一級調(diào)用，繼續(xù)探測
        if cur == len(mark):
            ret.append(self.make(mark))
            return

        #試探處理，將當前行的皇后應該在的位置遍歷每一列，如果滿足條件，遞歸調(diào)用處理下一行
        for i in range(len(mark)):
            mark[cur], down = i, True
            for j in range(cur):
                if mark[j] == i or abs(i-mark[j]) == cur - j:
                    down = False
                    break
            if down:
                self.recursive(mark, cur+1, ret)

    def solveNQueens(self, n):

        ret = []
        self.recursive([None]*n, 0, ret)
        return ret

enity = Solution()
print enity.solveNQueens(4)