Last active
February 12, 2019 01:14
-
-
Save juancresc/f127baa9f9febd568a86694e422ba3d0 to your computer and use it in GitHub Desktop.
A solution to 8 queen problem in python3
This file contains hidden or 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
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