Skip to content

Instantly share code, notes, and snippets.

@juancresc
Last active February 12, 2019 01:14
Show Gist options
  • Save juancresc/f127baa9f9febd568a86694e422ba3d0 to your computer and use it in GitHub Desktop.
Save juancresc/f127baa9f9febd568a86694e422ba3d0 to your computer and use it in GitHub Desktop.
A solution to 8 queen problem in python3
import itertools
def valid(solution):
col_1 = 0
for row_1 in solution:
row_1 = int(row_1)
col_2 = 0
for row_2 in solution:
row_2 = int(row_2)
if col_1 != col_2: # do not compare to itself
if col_1 == col_2: # same column? not gonna happend, but I want to leave it here as a guide
return False
if row_1 == row_2: # same row
return False
if abs(row_1 - row_2) == abs(col_1 - col_2): # same diagonal
return False
col_2 += 1
col_1 += 1
return True
#a putative solution is saved as an 8-array where the n-th element is the row and n is the column
#for example the first permutation 01234567 will have queens in the main diagonal of the board
#we use permutation as we don't want duplicated rows (columns won't be duplicated because the position is the col)
solutions = itertools.permutations('01234567')
count = 0
count_solutions = 0
for solution in solutions:
solution = list(solution)
if valid(solution):
count_solutions += 1
#print(solution) # you want to see the solutions?
count += 1
print("I've tried %i times and found %i solutions" % (count, count_solutions))
#outputs: I've tried 40320 times and found 92 solutions
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment