Skip to content

Instantly share code, notes, and snippets.

@gubatron
Last active April 19, 2022 22:04
Show Gist options
  • Save gubatron/0c85481d36caa57fa36f9cb346618e70 to your computer and use it in GitHub Desktop.
Save gubatron/0c85481d36caa57fa36f9cb346618e70 to your computer and use it in GitHub Desktop.
eight_queens.py - Decent brute force 8 queens state finder (takes about 235k iterations)
from random import shuffle
'''
This module tries to solve the 8 queens problem.
'''
identity_rows = [0, 1, 2, 3, 4, 5, 6, 7]
def queens_attack_each_other(queen_a, queen_b):
'''True if 2 queens face each other'''
return queen_a[0] == queen_b[0] or queen_a[1] == queen_b[1] or abs(queen_a[0] - queen_b[0]) == abs(queen_a[1] - queen_b[1])
def solution_found(state):
return count_collision(state) == 0
def count_collision(state, breakOnFirstCollision=True):
'''Checks current queens, if one attacks another it returns False'''
hits = 0
for queen_a in state:
for queen_b in state:
if queen_a != queen_b and queens_attack_each_other(queen_a, queen_b):
hits += 1
if breakOnFirstCollision:
return hits
return hits
def generate_random_state():
'''Generates a random state'''
unsorted_rows = identity_rows.copy()
shuffle(unsorted_rows)
state = []
for i in range(8):
state.append([i, unsorted_rows.pop()])
return state
if __name__ == '__main__':
solutions_found = []
generated_states = 0
print('Searching for solution...')
while len(solutions_found) < 92:
s = generate_random_state()
generated_states += 1
if solution_found(s) and s not in solutions_found:
solutions_found.append(s)
print(
f'Solution {len(solutions_found)}. {generated_states} random states generated.')
print(s)
print()
# sample output
'''
Solution 1. 296 random states generated.
[[0, 6], [1, 3], [2, 1], [3, 7], [4, 5], [5, 0], [6, 2], [7, 4]]
Solution 2. 417 random states generated.
[[0, 2], [1, 5], [2, 1], [3, 6], [4, 0], [5, 3], [6, 7], [7, 4]]
Solution 3. 841 random states generated.
[[0, 1], [1, 4], [2, 6], [3, 0], [4, 2], [5, 7], [6, 5], [7, 3]]
Solution 4. 1131 random states generated.
[[0, 2], [1, 6], [2, 1], [3, 7], [4, 4], [5, 0], [6, 3], [7, 5]]
Solution 5. 1213 random states generated.
[[0, 4], [1, 2], [2, 0], [3, 6], [4, 1], [5, 7], [6, 5], [7, 3]]
Solution 6. 1922 random states generated.
[[0, 5], [1, 3], [2, 6], [3, 0], [4, 7], [5, 1], [6, 4], [7, 2]]
Solution 7. 2460 random states generated.
[[0, 7], [1, 3], [2, 0], [3, 2], [4, 5], [5, 1], [6, 6], [7, 4]]
Solution 8. 2540 random states generated.
[[0, 4], [1, 6], [2, 1], [3, 5], [4, 2], [5, 0], [6, 3], [7, 7]]
Solution 9. 2747 random states generated.
[[0, 4], [1, 1], [2, 5], [3, 0], [4, 6], [5, 3], [6, 7], [7, 2]]
Solution 10. 5015 random states generated.
[[0, 1], [1, 6], [2, 4], [3, 7], [4, 0], [5, 3], [6, 5], [7, 2]]
Solution 11. 5578 random states generated.
[[0, 3], [1, 1], [2, 6], [3, 2], [4, 5], [5, 7], [6, 0], [7, 4]]
Solution 12. 5829 random states generated.
[[0, 5], [1, 1], [2, 6], [3, 0], [4, 2], [5, 4], [6, 7], [7, 3]]
Solution 13. 6321 random states generated.
[[0, 3], [1, 1], [2, 4], [3, 7], [4, 5], [5, 0], [6, 2], [7, 6]]
Solution 14. 8650 random states generated.
[[0, 5], [1, 2], [2, 0], [3, 7], [4, 3], [5, 1], [6, 6], [7, 4]]
Solution 15. 8956 random states generated.
[[0, 1], [1, 4], [2, 6], [3, 3], [4, 0], [5, 7], [6, 5], [7, 2]]
Solution 16. 9024 random states generated.
[[0, 2], [1, 4], [2, 1], [3, 7], [4, 5], [5, 3], [6, 6], [7, 0]]
Solution 17. 9895 random states generated.
[[0, 4], [1, 2], [2, 0], [3, 5], [4, 7], [5, 1], [6, 3], [7, 6]]
Solution 18. 10431 random states generated.
[[0, 0], [1, 6], [2, 3], [3, 5], [4, 7], [5, 1], [6, 4], [7, 2]]
Solution 19. 10495 random states generated.
[[0, 5], [1, 3], [2, 1], [3, 7], [4, 4], [5, 6], [6, 0], [7, 2]]
Solution 20. 10683 random states generated.
[[0, 3], [1, 1], [2, 7], [3, 5], [4, 0], [5, 2], [6, 4], [7, 6]]
Solution 21. 11801 random states generated.
[[0, 5], [1, 7], [2, 1], [3, 3], [4, 0], [5, 6], [6, 4], [7, 2]]
Solution 22. 12173 random states generated.
[[0, 5], [1, 2], [2, 4], [3, 7], [4, 0], [5, 3], [6, 1], [7, 6]]
Solution 23. 12465 random states generated.
[[0, 4], [1, 6], [2, 1], [3, 5], [4, 2], [5, 0], [6, 7], [7, 3]]
Solution 24. 13451 random states generated.
[[0, 3], [1, 7], [2, 0], [3, 2], [4, 5], [5, 1], [6, 6], [7, 4]]
Solution 25. 13962 random states generated.
[[0, 4], [1, 1], [2, 7], [3, 0], [4, 3], [5, 6], [6, 2], [7, 5]]
Solution 26. 15093 random states generated.
[[0, 2], [1, 5], [2, 7], [3, 0], [4, 3], [5, 6], [6, 4], [7, 1]]
Solution 27. 15115 random states generated.
[[0, 4], [1, 0], [2, 7], [3, 5], [4, 2], [5, 6], [6, 1], [7, 3]]
Solution 28. 16165 random states generated.
[[0, 4], [1, 6], [2, 0], [3, 2], [4, 7], [5, 5], [6, 3], [7, 1]]
Solution 29. 16200 random states generated.
[[0, 1], [1, 5], [2, 0], [3, 6], [4, 3], [5, 7], [6, 2], [7, 4]]
Solution 30. 17573 random states generated.
[[0, 3], [1, 1], [2, 6], [3, 2], [4, 5], [5, 7], [6, 4], [7, 0]]
Solution 31. 18154 random states generated.
[[0, 3], [1, 6], [2, 2], [3, 7], [4, 1], [5, 4], [6, 0], [7, 5]]
Solution 32. 18894 random states generated.
[[0, 2], [1, 4], [2, 1], [3, 7], [4, 0], [5, 6], [6, 3], [7, 5]]
Solution 33. 19540 random states generated.
[[0, 2], [1, 5], [2, 7], [3, 0], [4, 4], [5, 6], [6, 1], [7, 3]]
Solution 34. 19963 random states generated.
[[0, 5], [1, 2], [2, 6], [3, 1], [4, 3], [5, 7], [6, 0], [7, 4]]
Solution 35. 20940 random states generated.
[[0, 3], [1, 5], [2, 0], [3, 4], [4, 1], [5, 7], [6, 2], [7, 6]]
Solution 36. 22918 random states generated.
[[0, 5], [1, 2], [2, 0], [3, 6], [4, 4], [5, 7], [6, 1], [7, 3]]
Solution 37. 23142 random states generated.
[[0, 6], [1, 2], [2, 0], [3, 5], [4, 7], [5, 4], [6, 1], [7, 3]]
Solution 38. 24120 random states generated.
[[0, 3], [1, 7], [2, 0], [3, 4], [4, 6], [5, 1], [6, 5], [7, 2]]
Solution 39. 24178 random states generated.
[[0, 6], [1, 4], [2, 2], [3, 0], [4, 5], [5, 7], [6, 1], [7, 3]]
Solution 40. 24275 random states generated.
[[0, 6], [1, 1], [2, 3], [3, 0], [4, 7], [5, 4], [6, 2], [7, 5]]
Solution 41. 24626 random states generated.
[[0, 2], [1, 5], [2, 3], [3, 0], [4, 7], [5, 4], [6, 6], [7, 1]]
Solution 42. 24870 random states generated.
[[0, 2], [1, 7], [2, 3], [3, 6], [4, 0], [5, 5], [6, 1], [7, 4]]
Solution 43. 25102 random states generated.
[[0, 5], [1, 3], [2, 6], [3, 0], [4, 2], [5, 4], [6, 1], [7, 7]]
Solution 44. 25129 random states generated.
[[0, 4], [1, 6], [2, 1], [3, 3], [4, 7], [5, 0], [6, 2], [7, 5]]
Solution 45. 25223 random states generated.
[[0, 5], [1, 2], [2, 0], [3, 7], [4, 4], [5, 1], [6, 3], [7, 6]]
Solution 46. 26445 random states generated.
[[0, 6], [1, 1], [2, 5], [3, 2], [4, 0], [5, 3], [6, 7], [7, 4]]
Solution 47. 27520 random states generated.
[[0, 4], [1, 2], [2, 7], [3, 3], [4, 6], [5, 0], [6, 5], [7, 1]]
Solution 48. 27565 random states generated.
[[0, 3], [1, 5], [2, 7], [3, 2], [4, 0], [5, 6], [6, 4], [7, 1]]
Solution 49. 27572 random states generated.
[[0, 5], [1, 2], [2, 4], [3, 6], [4, 0], [5, 3], [6, 1], [7, 7]]
Solution 50. 27658 random states generated.
[[0, 3], [1, 5], [2, 7], [3, 1], [4, 6], [5, 0], [6, 2], [7, 4]]
Solution 51. 27956 random states generated.
[[0, 1], [1, 3], [2, 5], [3, 7], [4, 2], [5, 0], [6, 6], [7, 4]]
Solution 52. 28312 random states generated.
[[0, 1], [1, 6], [2, 2], [3, 5], [4, 7], [5, 4], [6, 0], [7, 3]]
Solution 53. 30058 random states generated.
[[0, 3], [1, 1], [2, 6], [3, 4], [4, 0], [5, 7], [6, 5], [7, 2]]
Solution 54. 31305 random states generated.
[[0, 3], [1, 0], [2, 4], [3, 7], [4, 1], [5, 6], [6, 2], [7, 5]]
Solution 55. 31317 random states generated.
[[0, 2], [1, 5], [2, 1], [3, 4], [4, 7], [5, 0], [6, 6], [7, 3]]
Solution 56. 32457 random states generated.
[[0, 6], [1, 3], [2, 1], [3, 4], [4, 7], [5, 0], [6, 2], [7, 5]]
Solution 57. 33949 random states generated.
[[0, 4], [1, 1], [2, 3], [3, 5], [4, 7], [5, 2], [6, 0], [7, 6]]
Solution 58. 34254 random states generated.
[[0, 7], [1, 2], [2, 0], [3, 5], [4, 1], [5, 4], [6, 6], [7, 3]]
Solution 59. 35405 random states generated.
[[0, 2], [1, 6], [2, 1], [3, 7], [4, 5], [5, 3], [6, 0], [7, 4]]
Solution 60. 37767 random states generated.
[[0, 4], [1, 6], [2, 0], [3, 3], [4, 1], [5, 7], [6, 5], [7, 2]]
Solution 61. 37982 random states generated.
[[0, 1], [1, 7], [2, 5], [3, 0], [4, 2], [5, 4], [6, 6], [7, 3]]
Solution 62. 38772 random states generated.
[[0, 6], [1, 2], [2, 7], [3, 1], [4, 4], [5, 0], [6, 5], [7, 3]]
Solution 63. 40053 random states generated.
[[0, 2], [1, 4], [2, 7], [3, 3], [4, 0], [5, 6], [6, 1], [7, 5]]
Solution 64. 41092 random states generated.
[[0, 2], [1, 5], [2, 7], [3, 1], [4, 3], [5, 0], [6, 6], [7, 4]]
Solution 65. 42234 random states generated.
[[0, 3], [1, 1], [2, 7], [3, 4], [4, 6], [5, 0], [6, 2], [7, 5]]
Solution 66. 42783 random states generated.
[[0, 5], [1, 0], [2, 4], [3, 1], [4, 7], [5, 2], [6, 6], [7, 3]]
Solution 67. 43079 random states generated.
[[0, 2], [1, 5], [2, 1], [3, 6], [4, 4], [5, 0], [6, 7], [7, 3]]
Solution 68. 45777 random states generated.
[[0, 3], [1, 6], [2, 4], [3, 1], [4, 5], [5, 0], [6, 2], [7, 7]]
Solution 69. 53104 random states generated.
[[0, 2], [1, 0], [2, 6], [3, 4], [4, 7], [5, 1], [6, 3], [7, 5]]
Solution 70. 54308 random states generated.
[[0, 4], [1, 6], [2, 3], [3, 0], [4, 2], [5, 7], [6, 5], [7, 1]]
Solution 71. 54943 random states generated.
[[0, 3], [1, 7], [2, 4], [3, 2], [4, 0], [5, 6], [6, 1], [7, 5]]
Solution 72. 57846 random states generated.
[[0, 6], [1, 0], [2, 2], [3, 7], [4, 5], [5, 3], [6, 1], [7, 4]]
Solution 73. 60375 random states generated.
[[0, 3], [1, 6], [2, 0], [3, 7], [4, 4], [5, 1], [6, 5], [7, 2]]
Solution 74. 61615 random states generated.
[[0, 3], [1, 0], [2, 4], [3, 7], [4, 5], [5, 2], [6, 6], [7, 1]]
Solution 75. 62720 random states generated.
[[0, 5], [1, 3], [2, 0], [3, 4], [4, 7], [5, 1], [6, 6], [7, 2]]
Solution 76. 63314 random states generated.
[[0, 5], [1, 1], [2, 6], [3, 0], [4, 3], [5, 7], [6, 4], [7, 2]]
Solution 77. 65238 random states generated.
[[0, 5], [1, 2], [2, 6], [3, 1], [4, 7], [5, 4], [6, 0], [7, 3]]
Solution 78. 74942 random states generated.
[[0, 4], [1, 7], [2, 3], [3, 0], [4, 6], [5, 1], [6, 5], [7, 2]]
Solution 79. 75881 random states generated.
[[0, 0], [1, 4], [2, 7], [3, 5], [4, 2], [5, 6], [6, 1], [7, 3]]
Solution 80. 81034 random states generated.
[[0, 4], [1, 0], [2, 7], [3, 3], [4, 1], [5, 6], [6, 2], [7, 5]]
Solution 81. 81716 random states generated.
[[0, 0], [1, 5], [2, 7], [3, 2], [4, 6], [5, 3], [6, 1], [7, 4]]
Solution 82. 87840 random states generated.
[[0, 4], [1, 1], [2, 3], [3, 6], [4, 2], [5, 7], [6, 5], [7, 0]]
Solution 83. 95556 random states generated.
[[0, 1], [1, 5], [2, 7], [3, 2], [4, 0], [5, 3], [6, 6], [7, 4]]
Solution 84. 101591 random states generated.
[[0, 0], [1, 6], [2, 4], [3, 7], [4, 1], [5, 3], [6, 5], [7, 2]]
Solution 85. 111439 random states generated.
[[0, 2], [1, 4], [2, 6], [3, 0], [4, 3], [5, 1], [6, 7], [7, 5]]
Solution 86. 111797 random states generated.
[[0, 3], [1, 6], [2, 4], [3, 2], [4, 0], [5, 5], [6, 7], [7, 1]]
Solution 87. 130771 random states generated.
[[0, 4], [1, 0], [2, 3], [3, 5], [4, 7], [5, 1], [6, 6], [7, 2]]
Solution 88. 134572 random states generated.
[[0, 5], [1, 2], [2, 6], [3, 3], [4, 0], [5, 7], [6, 1], [7, 4]]
Solution 89. 135882 random states generated.
[[0, 7], [1, 1], [2, 4], [3, 2], [4, 0], [5, 6], [6, 3], [7, 5]]
Solution 90. 178089 random states generated.
[[0, 7], [1, 1], [2, 3], [3, 0], [4, 6], [5, 4], [6, 2], [7, 5]]
Solution 91. 191286 random states generated.
[[0, 4], [1, 7], [2, 3], [3, 0], [4, 2], [5, 5], [6, 1], [7, 6]]
Solution 92. 235181 random states generated.
[[0, 2], [1, 5], [2, 3], [3, 1], [4, 7], [5, 4], [6, 6], [7, 0]]
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment