Created
December 6, 2015 08:10
-
-
Save addie/38af27b36eee08ef2b5e to your computer and use it in GitHub Desktop.
Solution to the N-Queens problem
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
# Three pretty print functions | |
def print_row(length): | |
for i in range(length): | |
print('+-', end="") | |
print('+') | |
def print_cell(array, length): | |
for i in range(length): | |
if i == array[0]: | |
print('|*', end="") | |
else: | |
print('| ', end="") | |
print("|") | |
def print_matrix(array): | |
"""Prints the queens n-matrix""" | |
array = list(map(int, array)) | |
length = len(array) | |
for i in range(length): | |
print_row(length) | |
print_cell(array[i:], length) | |
print_row(length) | |
print() | |
# Wrapper | |
def n_queens(row): | |
permutations = [] | |
return _permute(row, 0, len(row)-1, permutations) | |
# Work is done here | |
def _permute(row, start, end, permutations): | |
"""Permutes all of the Queen column positions and then checks | |
if the Queen is in a valid position before appending it to the returned array""" | |
if (start == end): | |
isValid = True | |
for i in range(len(row)-1): # checks if in same row or diagonal | |
if (row[i] == row[i+1] or | |
row[i] == row[i+1]+1 or | |
row[i] == row[i+1]-1): | |
isValid = False | |
if isValid: | |
string = ''.join(map(str, row)) | |
permutations.append(string) | |
else: | |
for i in range(start, end+1): | |
row[start], row[i] = row[i], row[start] # swap | |
_permute(row, start+1, end, permutations) | |
row[start], row[i] = row[i], row[start] # swap | |
return permutations | |
rows = list(range(5)) | |
permutations = n_queens(rows) | |
for index, valid_solution in enumerate(permutations): | |
print('Solution', index+1) | |
print_matrix(valid_solution) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment