n_queens.py

Board = List[List[bool]]

def print_board(board: Board) -> None:
    for row in board:
        for space in row:
            print('Q' if space else '.', end='')
        print()
    print()

def create_board(n: int) -> Board:
    return [
        [False] * n
        for _ in range(n)
    ]

def copy_board(board: Board) -> Board:
    # return [
    #     [space for space in board]
    #     for row in board
    # ]
    n = len(board)
    new_board = create_board(n)
    for i in range(n):
        for j in range(n):
            if board[i][j]:
                new_board[i][j] = True
    return new_board

def can_place(board: Board, row: int, col: int) -> bool:
    n = len(board)
    # horizontally
    # for i in range(n):
    #     if board[row][i]:
    #         return False
        
    # vertical
    for i in range(n):
        if board[i][col]:
            return False
    
    # diagonally
    for i in range(n):
        if (0 <= row-i < n) and (0 <= col-i < n) and board[row-i][col-i]:
            return False
    for i in range(n):
        if (0 <= row-i < n) and (0 <= col+i < n) and board[row-i][col+i]:
            return False
    return True


def solve(board: Board, queen_num: int) -> List[Board]:
    n = len(board)
    
    # print_board(board)
    solved_boards = []
    
    if queen_num == n:
        return [board]
    
    for i in range(n):
        if can_place(board, queen_num, i):
            # print_board(board)
            new_board = copy_board(board)
            new_board[queen_num][i] = True
            more_solved_boards = solve(new_board, queen_num + 1)
            solved_boards.extend(more_solved_boards)
            
    return solved_boards
            
    
    
# def translate_board(board: Board) -> List[str]:
#     for 

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = create_board(n)
        # print_board(board)
        all_boards = solve(board, 0)
        for a_board in all_boards:
            print_board(a_board)
        return all_boards