8 Queens Problem

To place 8 queens on the board, such that no two queens attack each other.

There are 64 spaces on an 8x8 board, and if each piece is placed on a square then 56 squares are left empty, number of combinations of arranging the queens without considering the rules of chess amounts to 4,426,165,368.

One way to approach the problem would be to place the first Queen at a designated square and try to place the subsequent Queens according to the rules of Chess.

In Chess, the queen can move any number of squares to the left, right, top and bottom. It can also move along diagonals of squares of the same colour. Therefore, in order to abide by the rules of chess one must ensure that only one Queen is placed for every row and for every column, whilst making sure that none of the Queens intersect the diagonals.

We can place the first Queen at a designated spot and try all the different possibilities of placing the subsequent Queens. When we have a Queen that is in the path of another, we can backtrack to one of the earlier placements we have done and try another position.

So for every row, only one Queen must be present and for every Column only one Queen must be present.

The positive diagonal elements are the Elements in the North-Eastern Diagonal of the Chessboard.

Get Pranav AVN’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Upon closer inspection, these elements have a constant value of Row number + Column Number:

Row + Column = k

The negative diagonal elements are the Elements in North-Western Diagonal of the Chessboard.

Upon closer inspection, these elements have a constant value of Row number — Column Number:

Row — Column = k

If an algorithm was to be devised for the same problem, it would involve recursion, as the problem at hand involves applying the same Validity check over a number of combinations, and requires subsequent steps only when the conditions fail.

def nQueens(n: int):
    col = set()
    posDiag = set()
    negDiag = set()

    res = 0
    def isValid(r):
        if r==n:
            nonlocal res
            res +=1
            return
        
        for c in range(n):
            if c in col or (r+c) in posDiag or (r-c) in negDiag:
                continue
            col.add(c)
            posDiag.add(r+c)
            negDiag.add(r-c)
            isValid(r+1)
            col.remove(c)
            posDiag.remove(r+c)
            negDiag.remove(r-c)

    isValid(0)
    return res

print(nQueens(8))

The above python code produces the result for an valid positions of 8 Queens on an 8x8 Chess board that do not attack each other.

When run, the program produces an answer of 92, stating that;
The number of valid possibilities for 8 Queens to be arranged on an 8x8 Chess board is 92, which is far shy of the initial estimate without considering validity(4,426,165,368).

However, the board has rotational symmetry on its 4 sides, therefore the actual answer to the problem at hand is 92/4 = 23.

The number of valid possibilities for 8 Queens to be arranged on an 8x8 Chess board is 23.

A repository of more such mathematical functions encountered in Electrical Engineering can be found here.