This isn't bad looking code. It's formatted nicely, and I think this is a good use of type hints.
My two main concerns are your naming, and your use of print.
Names should be snake_case according to PEP8. You started adhering to it, then reverted back to camelCase later. It can be a hard change to make if you're used to other languages, but it's proper for Python, and studies have shown that it's easier to read anyways.
I think you're "abusing" print here.
print_board is printing the board instead of returning a representation that can be used elsewhere. I'd change it to format_board (or stringify_board or something similar), and have it return a string instead of forcibly printing the board. It would be a fairly trivial change too. Just concatenate the different printed strings together, replace the print() calls with a "\n", and change your imperative for loop to a list comprehension that you give to join after. It would honestly probably be shorter and cleaner after those changes anyways.
Then elsewhere, like in solve, you're printing the results. I would instead return some kind of indicator value, like an Enum instead of printing there.
Why bother with limiting print? Testing and portability. Say you wanted to programmatically test print_board. You would need to intercept sys.stdin to get the printed text to compare it against a known string. This is both slower and more complicated than just having a function that returns a string in the first place. The same goes for solve. To test that's its operating correctly, you need to verify what it's printing instead of just checking the return value.
Forcing use of print also prevents you from using these function in any other context, like a Tkinter UI.
Return the data and let the caller decide how they want to use it.
If you really want a print_board function for convenience, just make a wrapper:
def print_board() -> None:
print(format_board())
Lastly, instead of using strings to indicate piece types, I'd use an Enum. Right now, you have a strong "Q" to indicate a queen on the board. Strings can be easily typo'd though; enums can't. If the only two valid board piece options are an empty space and a queen, you should use an enum to not only make that explicitly stated, but to enforce it. Entering an invalid enum invalid enum value will lead to an error instead of code-dependant effects that may end lead to silent failures.
I also realized just as I was about to submit this that your print_board and backtrack functions are relying on the global board defined in the "main". Don't do this! If those functions require data like board, that data should be explicitly passed in as arguments. If you wanted to test those functions, you wouldn't be able to just generate a dummy board in the console and pass it in. You would need to modify the global, run the function, then remember to modify to global again before further testing. The less relience you have on global variables, the easier your code will be to test and comprehend. Ideally, functions should accept as arguments all the data that they require, and return all data that they produce. This isn't always feasible, but it's a good design choice to pick unless you have a good reason to rely on globals (like board) and side-effects (like print).
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()
