I'm on my phone, so this is going to be a relatively poor review.
Now that I'm on my full computer, I'm able to take a better look at the code and play with it a little more.
First, here's the enum usage that I was referring to. Ignore my previous suggestion for solve
. I realized that an enum wasn't really appropriate there (I'll show my alternate suggestion after). Basically, BoardSquare
represents the total possible states of each square on the board, along with the string representations that they have:
from enum import Enum
class BoardSquare(Enum): # A square on the board can either be a queen, or an empty space
QUEEN = "Q"
EMPTY = " "
With that, I decided to use some slightly more advanced type hinting and created an alias for the board:
from typing import List
Board = List[List[BoardSquare]] # A Board is a list of lists of board squares
This, combined with the enum ensures that nothing except a QUEEN
or EMPTY
is ever put into a board. Attempting to do so will cause a warning. This helps prevent typos:
board: Board = [[BoardSquare.EMPTY] * side_length for _ in range(side_length)]
board[1][2] = "SOME INVALID DATA" # Causes an "Unexpected types" warning
And here's my format_board
that I came up with:
# A helper to neaten up format_board
def _format_row(row: List[BoardSquare]) -> str:
return '| ' + ' | '.join(square.value for square in row) + ' |' # .value is the string defined in the enum
def format_board(board: Board) -> str:
""" Formats the board as a string """
board_length = len(board) # Instead of relying on the global SIZE, I'd just compute it
print_side_length = 3 * (board_length - 1) + board_length + 4
top_bottom_str = '-' * print_side_length # Might as well save this instead of writing the same thing twice.
# I'll admit, this got a little more convoluted than I thought it would. It's just nested called to `join `though.
return top_bottom_str + "\n" \
+ '\n'.join(_format_row(row) + '\n' + top_bottom_str for row in board)
Yes, as the comments note, this got a little longer than I though it would. The need to translate the enum into a string using the generator expression necessitated breaking off the formatting of each row into its own function for readability.
After going around and touching up some other stuff (see the comments), here's the full code that I ended up with:
from typing import List
from enum import Enum
class BoardSquare(Enum): # A square on the board can either be a queen, or an empty space
QUEEN = "Q"
EMPTY = " "
Board = List[List[BoardSquare]] # A Board is a list of lists of board squares
# Make it easier to create a new board for testing purposes
def new_board(side_length: int) -> Board:
return [[BoardSquare.EMPTY] * side_length for _ in range(side_length)]
# A helper to neaten up format_board
def _format_row(row: List[BoardSquare]) -> str:
return '| ' + ' | '.join(square.value for square in row) + ' |' # .value is the string defined in the enum
def format_board(board: Board) -> str:
""" Formats the board as a string """
board_length = len(board) # Instead of relying on the global SIZE, I'd just compute it
print_side_length = 3 * (board_length - 1) + board_length + 4
top_bottom_str = '-' * print_side_length # Might as well save this instead of writing the same thing twice.
# I'll admit, this got a little more convoluted than I thought it would. It's just nested called to `join `though.
return top_bottom_str + "\n" \
+ '\n'.join(_format_row(row) + '\n' + top_bottom_str for row in board)
def print_board(board: Board) -> None:
""" Prints the board """
print(format_board(board))
def is_valid(row: int, col: int) -> bool:
""" Returns if a cell index is valid """
return 0 <= row < GLOBAL_SIZE and 0 <= col < GLOBAL_SIZE
def is_safe(row: int, col: int) -> bool:
""" Checks if the given index position is safe """
# Checks if the column is safe
for i in range(GLOBAL_SIZE):
if i != row and global_board[i][col] != BoardSquare.EMPTY:
return False
# Checks if the row is safe
for j in range(GLOBAL_SIZE):
if j != col and global_board[row][j] != BoardSquare.EMPTY:
return False
# Checks if the diagonals are safe
for k in range(GLOBAL_SIZE):
if is_valid(row + k, col + k) and global_board[row + k][col + k] != BoardSquare.EMPTY or \
is_valid(row - k, col + k) and global_board[row - k][col + k] != BoardSquare.EMPTY or \
is_valid(row + k, col - k) and global_board[row + k][col - k] != BoardSquare.EMPTY or \
is_valid(row - k, col - k) and global_board[row - k][col - k] != BoardSquare.EMPTY:
return False
return True
def backtrack(row=0, total=0) -> int: # I changed this to int. It was bool before, but that was wrong
""" Backtracks and fills checks for every possible combination """
# If all rows are safely filled with queens
if row == GLOBAL_SIZE:
# print_board(global_board) # Uncomment the code to print the current solution
# input('Enter to continue... ')
return 1
for col in range(GLOBAL_SIZE):
# If the current index is safe, check for the next row
if is_safe(row, col):
global_board[row][col] = BoardSquare.QUEEN # Use the enums values here instead
total += backtrack(row + 1)
global_board[row][col] = BoardSquare.EMPTY
return total
def report_solution() -> None:
""" Calls backtrack and prints number of solutions """
total = backtrack()
print()
if not total:
print('No possible solution was found')
elif total == 1:
print('There is a total of 1 solution')
else:
print(f'There are a total of {total} solutions')
if __name__ == '__main__':
GLOBAL_SIZE = int(input('Enter the size of the board: '))
global_board = new_board(GLOBAL_SIZE)
report_solution()