6.25 - hard - 12

51. N-Queens
比较经典的backtracking的问题， backtracking就是要1.循环的条件，2进入的条件和状态，3.退出后的状态

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        board = [["." for _ in range(n)] for _ in range(n)]
        self.res = []
        self.dfs(board, 0)
        return self.res
    
    def dfs(self, board, i): # put chess on ith row
        if i == len(board):
            # print board
            self.res.append(["".join(x) for x in board])
            return
        
        for j in range(len(board[0])):
            # 对于所有列
            if self.valid(board, i, j):
                board[i][j] = 'Q'
                self.dfs(board, i+1)
                board[i][j] = '.'
    
    def valid(self, board, i, j):
        # valid row
        if 'x' in board[i]:
            return False
        
        # valid col
        for k in range(len(board)):
            if board[k][j] == 'Q':
                return False
        
        # valid diag
        for k in range(len(board)):
            col = k + j - i
            if 0 <= col < len(board) and board[k][col] == 'Q':
                return False
        
        # valid antidiag
        for k in range(len(board)):
            col = i + j - k
            if 0 <= col < len(board) and board[k][col] == 'Q':
                return False
        return True