I just tried to create a program for the N queens problem.
def print_board() -> None:
""" Prints the board """
length = 3 * (SIZE - 1) + SIZE + 4
print()
print('-' * length)
for row in board:
print('| ' + ' | '.join(row) + ' |')
print('-' * length)
print()
def isValid(row: int, col: int) -> bool:
""" Returns if a cell index is valid """
return 0 <= row < SIZE and 0 <= col < SIZE
def isSafe(row: int, col: int) -> bool:
""" Checks if the given index position is safe """
# Checks if the column is safe
for i in range(SIZE):
if i != row and board[i][col] != ' ':
return False
# Checks if the row is safe
for j in range(SIZE):
if j != col and board[row][j] != ' ':
return False
# Checks if the diagonals are safe
for k in range(min(SIZE, SIZE)):
if isValid(row + k, col + k) and board[row + k][col + k] != ' ' or \
isValid(row - k, col + k) and board[row - k][col + k] != ' ' or \
isValid(row + k, col - k) and board[row + k][col - k] != ' ' or \
isValid(row - k, col - k) and board[row - k][col - k] != ' ':
return False
return True
def backtrack(row=0, total=0) -> bool:
""" Backtracks and fills chacks for every possible combination """
# If all rows are safely filled with queens
if row == SIZE:
# print_board() # Uncomment the code to print the current solution
# input('Enter to continue... ')
return 1
for col in range(SIZE):
# If the current index is safe, check for the next row
if isSafe(row, col):
board[row][col] = 'Q'
total += backtrack(row + 1)
board[row][col] = ' '
return total
def solve() -> 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__':
SIZE = int(input('Enter the size of the board: '))
board = [[' '] * SIZE for row in range(SIZE)]
solve()
Though it does work, I'm not satisfied. I want to make this code as short as possible while also following Pep8 rules.
I believe there isn't a faster approach, but if there are any, please enlighten me!
Thank you!