6.25 - hard - 13

52. N-Queens II

和上一题基本没什么区别

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        board = [["." for _ in range(n)] for _ in range(n)]
        self.count = 0
        self.dfs(board, 0)
        return self.count
    
    def dfs(self, board, i): # put chess on ith row
        if i == len(board):
            # print board
            self.count += 1
            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