Skip to content

Instantly share code, notes, and snippets.

@shyal
Created January 18, 2020 13:00
Show Gist options
  • Save shyal/81cfef41eadfb77711eb89719fac7d9e to your computer and use it in GitHub Desktop.
Save shyal/81cfef41eadfb77711eb89719fac7d9e to your computer and use it in GitHub Desktop.
n-queen algorithm animated in the terminal
from time import sleep
from os import system
"""
After spending the day trying to understand this algorithm, i decided to animated it in terminal.
Makes a lot more sense, so sharing.
"""
delay = .05
def n_queens(n):
def solve_n_queens(row, col_placement):
if row == n:
print("HURRAH!")
sleep(1)
result.append(col_placement.copy())
return
for col in range(n):
# Test if a newly placed queen will conflict
# any earlier queens placed before.
conflict = False
cols_to_backtest = col_placement[:row]
to_test = col_placement[:]
to_test[row] = col
for i, c in enumerate(cols_to_backtest):
if abs(c - col) in (0, row - i):
conflict = True
break
print('\n'*5)
system('clear')
if not conflict:
col_placement[row] = col
draw_board(col_placement)
sleep(delay)
solve_n_queens(row + 1, col_placement[:])
else:
draw_board(to_test, row, col, conflict)
sleep(delay)
result = []
solve_n_queens(0, [-1] * n)
return result
def comp(a, b):
return sorted(a) == sorted(b)
def draw_board(queens, row=-1, col=-1, conflict=False):
n = len(queens)
for i in range(n):
print(' |', end='')
for j in range(n):
print('---|', end='')
print('')
if queens[i] != -1:
print(f' {queens[i]} |', end='')
else:
print(f' |', end='')
for j in range(n):
if queens[i] == j:
c = 'o'
if i == row and j == col:
c = '.'
if conflict:
c = 'x'
else:
c = ' '
print(' {} |'.format(c), end='')
print('')
system('clear')
for queens in n_queens(6):
draw_board(queens)
print(' '+'-'*17)
pass
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment