Created
July 25, 2020 20:15
-
-
Save brianhelba/5d916df464358efcbd1b6262cb3ccb82 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment