回溯算法--LC51.N皇后

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        # 回溯问题
        # 皇后们的约束条件：
            # 1.不能同行
            # 2.不能同列
            # 3.不能同斜线
        # 先把棋盘创建出来，默认都是"."
        board = [["."]*n for _ in range(n)]
        result = list()
        def backtracking(board, n, row):
            # 终止条件
            if row == n:
                temp = list()
                for i in board:
                    temp_ = ''.join(i)
                    temp.append(temp_)
                result.append(temp)
            for col in range(n):
                if not self.valid(board, row, col, n):
                    continue
                board[row][col] = 'Q'
                backtracking(board, n, row+1)
                # 回溯
                board[row][col] = '.'
        backtracking(board, n, 0)
        return result
    def valid(self, board, row, col, n):
        # 行不用判断，因为每行都选一个，肯定不会同行
        # 先判断列
        for i in range(n):
            if board[i][col] == 'Q':
                return False
        # 判断左上角
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # 判断右上角
        i = row -1
        j = col +1 
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True