Investigation on N – queens problem using backtracking algorithm

Watching a movie, I came across thieves who would break into lockers. This is the point from where it all started. It planted the seed in my mind but my thoughts gained momentum when I was taken to my uncle's house who owned a locker factory.

It was during my summer vacation and hence was a long stay. Talking to my uncle about lockers, he finally agreed to take me to the factory. It was a beautiful experience there I began taking more interest on how safety is assured in lockers.

I began surfing internet in order to know more and more about this. It was during this research when I came across a term called the '8 Queen's Problem'.

I tried to gather as much information as possible. I read quite a few discreate mathematics journals, algorithms, coding using python and much more. Despite all, I could not locate the solution anywhere, hence this IA.

In this IA, I have tried and found out the solution to the 8 Queen's Problem.

The main motive of this IA is to find the 8 – queens problem using backtracking algorithm. As the backtracking algorithm is predominantly used for solvation of N – Queens problem, thus, solution of 2 – Queens problem, 3 – Queens problem and 4 – Queens problem are the corollary objectives of this IA.

What are the solutions of 8 – Queens Problem?

The game of chess is one of the ancient games that is still played in current time without making intensive changes. Originating in the time where the empires were ruled by the emperors, the game showcases similar kind of scenario. It ascertains a scene of a battlefield where two emperors fight with each other using their army. The chess is a game of patience and strategy which tests the intelligence of the players in today’s world. The chess board is not only a square of certain blocks; for mathematicians, it is a maze of combination of several mathematical tools.

A chess board is a square board which consists of 8 rows and 8 columns; resulting in formation of 64 distinct blocks. According to the rule of chess, a queen can move vertically, horizontally and diagonally in these blocks. If any other item of chess comes in the way of a queen, then the queen will eliminate the other item.

The 8 – Queens Problem is a special mathematical question which demands an orientation, such that 8 queens will not eliminate each other despite of placing all the queens in the same chess board.

Chess board is a fusion of different mathematical concepts and tools. It shows the property of symmetry and reflection. Thus, any particular orientation can be transformed into other orientations without affecting the game using the principles of geometry.

In this particular IA, as it can be solved only using trial and error method, it falls under the category of discrete mathematics. The most efficient method of solving these kinds of problems is using Greedy’s method. A special type of application of Greedy’s method is the Backtracking Algorithm. It provides use with a certain number of rules which should be followed in order to attain the goal to solve the 8 – Queens Problem.

The steps of Backtracking Algorithm are mentioned as follows:

• The queens should be placed row-wise.
• Firstly, the first queen should be placed at the first position, i.e., first row and first column (topmost left corner) in the chess board.
• The second queen should be placed in the next row. In order to choose the column, it is necessary to start from left, proceeding towards the right side considering each column one by one. In the first column, in which the queen can be placed without getting attacked by the previous queen, the second queen should be placed.
• The same process should be followed unless the situation comes in which no particular column is left available for a queen to place in the current row.
• If such case, it is required to move back to the previous row and select a column in which the queen is safe.
• If the above step is successful then Step (iii) should be followed. If the above step is not successful then Step (v) should be followed again.

There is no particular operation of 8 – Queens Problem for Backtracking Algorithm. Rather, the algorithm is designed for N – Queens Problem where N is the number of rows, columns and queens. In order to make the IA simpler and mathematically enriched, this algorithm will be used only to find one particular solution of the 8 – Queens problem and the remaining solutions will be found using the properties of symmetry and reflection. In this IA, all the problems mentioned in the Aim will be solved mathematically using the algorithm but as this process is very long and very simple, in order to solve the 8 – Queens Problem, a programming language will be used to simulate the result.

There are certain limitations of N – Queens Problem which will be mathematically explored in this IA.

Finally, 8 – Queens Problem is a puzzle which is used in encryption or security code such as a lock. This is because the probability of getting the solution if attempted randomly is almost equal to zero and this will be shown in this IA using Combination.

The formula of Combination is shown below where n is the total number of events and r is the number of sample spaces in the expression:

\(C^n_r = \frac{n!}{r!\ × \ (n-r)!}\)

The formula of Probability is also given below where P is the possible number of events and S is the total number of events in the expression:

Probability = \(\frac{P}{S}\)

In this process of calculation, green cells of table signify the position at which a queen has been placed and red cells signifies no available blocks for a queen as those blocks are accessible by the previously placed queens in the rows above the present row.

In this particular problem, the chess board comprises two rows and two columns. The problem is the place 2 queens in the board such that one queen will not attack the other.

The solution of this problem is shown below using back tracking algorithm:

Both the columns are not available for a queen to place.

Still no column is available for a queen in the second row.

Thus, there is no solution of 2 – Queens Problem. This is a limitation of N – Queens Problem.

In this particular problem, the chess board comprises three rows and three columns. The problem is the place 3 queens in the board such that one queen will not attack the other.

The solution of this problem is shown below using back tracking algorithm:

All the columns are not available for a queen to place.