Solve the 8 Queens Problem in Python

Before starting, let me clarify that this solution is neither the best of time complexity nor the most efficient. However, I found this solution to be easy to understand and code, and it solves them in a quick time.

There are some algorithms that use Backtracking or Branch and Bound, which require understanding in specific algorithms. Our approach is based on brute force, but intelligent brute force with a module called Itertools. First, let’s talk about some math.

Levels of Brute Force

Our objective is to go through the least possible arrangements to check the conditions. We will start with the worst and make tiny adjustments.

• Arrangements of 8 queens in 64 sections. There are 64 possible places, so we need to choose 8 to place the queens there. This can be done in 64C8 = (64x63x62x61x60x59x58x57)/8! = 4,426,165,368 ways.

• **Arrangements of 1 queen per row. **If we restrict one queen per row, each queen has 8 possible places, so the total arrangements is 8⁸ = 16,777,216 ways. This is approximately 264 times better than the previous one. In python, this can be achieved by nested for loops.

• **Permutations of 8 queens, 1 queen per row. **Can we do better than the previous? Of course! If we only take care of the permutations of the numbers 1 to 8, and map the first place to row 1, the second place to row 2, and so on, we do not worry anymore about being in the same row or being in the same column. The total arrangements in this case is 8! = **40,320, **416 times better than the previous!

For this, we are going to use a special python module called Itertools. The program below prints all the permutations of a list.

#Permutations mapped to the board
from itertools import permutations

list = list(range(8))
perms = permutations(list)

for perm in perms:
print(perm)

Process of Coding

The idea is to place the queens one by one in the order of the permutations. If another queen cannot be placed, then we discard that permutation and go to the next one.

Initialize the table

All the table will be initialized to 0.

table = [[0]*8 for _ in range(8)]

Print the table

def print_table():
    for row range(8):
        print(table[row])

Place a queen

• An empty square is 0

• An attacked square is 1

• A square occupied by a queen is a 2

  def put_queen(x,y): if table[y][x] == 0: for m in range(8):

            table[y][m] = 1
            table[m][x] = 1
            table[y][x] = 2
  
            if y+m <= 7 and x+m <= 7:
                table[y+m][x+m] = 1
            if y-m >= 0 and x+m <= 7:
                table[y-m][x+m] = 1
            if y+m <= 7 and x-m >= 0:
                table[y+m][x-m] = 1
            if y-m >= 0 and x-m >= 0:
                table[y-m][x-m] = 1
        return True
    else:
        return False
  

We first check if the queen can be placed in the coordinates (x, y). If so, the first for loop with variable m is filling the whole column and the whole row. We then fill the diagonals with a condition to avoid the index error.

Nested if statements for each permutation

Here now comes the core of the intelligent brute force. For every permutation, check if you can put the queen. If not, break the process and go on with the next permutation. If the 8 queens are placed, print the table.

list = list(range(8))
perms = itertools.permutations(list)

num_comb = 0

for perm in perms:
    if put_queen(perm[0], 0) == True:
        if put_queen(perm[1], 1) == True:
            if put_queen(perm[2], 2) == True:
                if put_queen(perm[3], 3) == True:
                    if put_queen(perm[4], 4) == True:
                        if put_queen(perm[5], 5) == True:
                            if put_queen(perm[6], 6) == True:
                                if put_queen(perm[7], 7) == True:
                                    print_table()
                                    num_comb += 1
                                    print(f"solution{num_comb}")
                                    print(" ")
    table = [[0] * 8 for _ in range(8)]

Run the program

The output will produce the 92 ways in which the queens can be arranged. For example, the first solution is:

[2, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 2, 1, 1]
[1, 1, 2, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 2, 1]
[1, 2, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 2, 1, 1, 1, 1]
solution number 1

So this is it! Thanks to our cases reduction, the following program runs in a second. Hope you liked this article!