eight_queens.py - Decent brute force 8 queens state finder (takes about 235k iterations)

eight_queens.py

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]]
'''