33.-n-queens.md

33. N-Queens

##　Challenge
##　Can you do it without recursion?
## 这不就是的要求我们用recursive
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # write your code here
        res = []
        M = [-1] * n # 一维数组表达queens 位置 idx 行, values col
        
        def bt(q_row,temp):
            if q_row == n: # 满queen
                res.append(self.decode(temp))
                
            for i in range(n):
                if self.isValid(temp, q_row,i):
                    temp[q_row] = i # 定义 该queen 的col
                    bt(q_row + 1,temp[:]) ## call
                    temp[q_row] = -1 ## 回溯
        bt(0,M)
        return res
    
    def isValid(self,tmp,row,col):
        ## 不能同行 
        for i in range(row): ## 肯定就找false快啦
            if tmp[i]== col or abs(row - i) == abs(col - tmp[i]):
                return False
        ## 不能同列
        ## 不能对角线
        return True
    
    def decode(self,m):
        M = [['.' for _ in range(len(m))] for _ in range(len(m))]
        # print(M,m)
        for i,v in enumerate(m):
            M[i][v]= 'Q'
        return list(map(lambda x : "".join(x),M))