N-Queens – Python 3 (Week 19 – 02)

class Solution:
    """
    @param: n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        # write your code here
        result = []
        self.dfs(n, [], result)
        return result
        
        
        
    def dfs(self, n, cols, result):
        row = len(cols)
        
        if row == n:
            result.append(self.draw_chessboard(cols))
            return
        
        for col in range(n):
            if not self.is_valid(cols, row, col):
                continue
            cols.append(col)
            self.dfs(n, cols, result)
            cols.pop()
            
    
    def is_valid(self, cols, row, col):
        for r, c in enumerate(cols):
            if c == col:
                return False
            if r - c == row - col or r + c == row + col:
                return False
        return True
        
    def draw_chessboard(self, cols):
        n = len(cols)
        board = []
        for i in range(n):
            row = ['Q' if j == cols[i] else '.' for j in range(n)]
            board.append(''.join(row))
        return board

class Solution:
    """
    @param: n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        # write your code here
        result = []
        
        visited = {
            'col': set(),
            'sum': set(),
            'diff': set(),
        }
        
        self.dfs(n, [], result, visited)
        return result
        
        
        
    def dfs(self, n, cols, result, visited):
        row = len(cols)
        
        if row == n:
            result.append(self.draw_chessboard(cols))
            return
        
        for col in range(n):
            if not self.is_valid(cols, visited, col):
                continue
            cols.append(col)
            visited['col'].add(col)
            visited['sum'].add(row + col)
            visited['diff'].add(row - col)
            self.dfs(n, cols, result, visited)
            visited['col'].remove(col)
            visited['sum'].remove(row + col)
            visited['diff'].remove(row - col)
            cols.pop()
            
        
    def is_valid(self, cols, visited, col):
        row = len(cols)
        if col in visited['col']:
            return False
        if row + col in visited['sum']:
            return False
        if row - col in visited['diff']:
            return False
        return True
        
    def draw_chessboard(self, cols):
        n = len(cols)
        board = []
        for i in range(n):
            row = ['Q' if j == cols[i] else '.' for j in range(n)]
            board.append(''.join(row))
        return board