Skip to
Investigation on N – queen’s problem using backtracking algorithm
Table of content
Rationale
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.
Aim
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.
Research question
What are the solutions of 8 – Queens Problem?
Introduction
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}\)
Process of calculation
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.
Queens problem
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.
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.
No block is available.
No block is available.
All the columns are not available for a queen to place.
The only space available is the column which is already been checked. Thus, there is no solution of 3 – Queens Problem. This is another limitation of N – Queens Problem.
Queens problem
In this particular problem, the chess board comprises four rows and four columns. The problem is the place 4 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.
All the columns are not available for a queen to place.
All the columns are not available for a queen to place in third row.
As a queen is already placed in the last column, thus again Step (vi) should be followed:
This is a valid solution of 4 – Queens Problem. Now, the other solution will be found using the principles of reflection. As the 4x4 Chess board is symmetrical, thus, another orientation of this solution can be obtained by mirroring the orientation vertically. The obtained solution will be:
By reflecting the obtained orientation of Step 12 horizontally, same solution will be derived. Thus, there are only two solutions of a 4 – Queens Problem.
Queens problem
In this particular problem, the chess board comprises eight rows and eight columns. The problem is the place 8 queens in the board such that one queen will not attack the other. In this particular case, a programming language will be used to find the solution of the problem. The code of the programming is written in Python 3. The code is shown below:
class NQueens:
self.size = size
self.solutions 0 =
self.solve()
def solve(self):
positions = [-1] * self.size
self.put_queen(positions, 0)
print("Found", self.solutions, "solutions.")
def put_queen(self, positions, target_row):
if target_row == self.size:
self.show_full_board(positions)
self.solutions += 1
else:
for column in range (self.size):
if self.check_place(positions, target_row, column):
positions[target_row] = column
self.put_queen(positions, target_row + 1)
def check_place(self, positions, ocuppiesd_rows, column):
for i in range (ocuppied_rows):
if positions[i] == column or \
positions[i] - i == column - ocuppies_rows or \
positions[i] + i == column + ocuppies_rows:
return False
return True
def show full board(self, positions):
for row in range(self.size):
line = ""
for column in range (self.size):
if positions[row] == column:
line += "Q "
else:
line += ". "
print(line)
print("\n")
def show_short_board(self, positions):
line = ""
for i in range(self.size):
line += str (positions[i]) + " "
print (line)
def main():
NQueens (8)
if_name_ == "_main_":
main()
Output of the code:
The output is shown by making columns in this Word File otherwise it will take a lot of unnecessary spacing.
Output of the code:
The output is shown by making columns in this Word File otherwise it will take a lot of unnecessary spacing.
There are 92 solutions of this problem.
Analysing the probability of correct orientation at a random
Queens problem
Total number of blocks present in a 4x4 Chess Board is 16 and the number of elements (queens) to be placed is 4. Thus, the total number of orientations that are possible for arranging 4 queens in a chess board is shown below using the formula of Combination:
\(C^n_r=\frac{n!}{r!×(n-r)!}\)
\(=>C^{16}_4=\frac{16!}{4!×(16-4)!}\)
\(=>C^{16}_4=\frac{16!}{4!\,×\,12!}\)
\(=>C^{16}_4=1820\)
The number of solutions of 4 – Queen’s Problem is 2.
Therefore, probability of getting a correct orientation by randomly placing the queens is shown below:
Probability \(=\frac{P}{S}\)
=> Probability = \(\frac{2}{1820}=\frac{1}{910}=1.098×10^{-3}\)
Queens problem
Total number of blocks present in a 8x8 Chess Board is 64 and the number of elements (queens) to be placed is 8. Thus, the total number of orientations that are possible for arranging 8 queens in a chess board is shown below using the formula of Combination:
\(C^n_r=\frac{n!}{r!\,×\,(n-r)!}\)
\(=>C^{64}_8=\frac{64!}{8!\,×\,(64-8)!}\)
\(=>C^{64}_8=\frac{64!}{8\,×\,56!}\)
\(=>C^{64}_8=\) 4426165368
The number of solutions of 8 – Queen’s Problem is 92.
Therefore, probability of getting a correct orientation by randomly placing the queens is shown below:
Probability = \(\frac{P}{S}\)
=> Probability = \(\frac{92}{4426165368}=2.078×10^{-8}\)
Conclusion
N – Queens Problem is one of the most tricky problems to solve and thus it is used as security key in several conditions. In this IA, solution of few N – Queen’s Problem has been solved using all the steps of the procedure using Backtracking Algorithm. However, assuming the number of pages required to solve each solution of 8 – Queens Problem from the solutions of 4 – Queens Problem, Python Programming Language has been used to solve the 8 – Queens Problem.
In this IA, initially, a few limitations of the N – Queens Problem has to be inferred. There are no solution set of 2 – Queens Problem and 3 – Queens Problem. Thus, from this IA, it can be suggested that, the value of N in N – Queens problem is greater than or equal to 4.
Consequently, in case of 4 – Queens problem, two solution set has been obtained. There is only one distinct set and the other one is obtained using the property of reflection. Thus, it should be noted that the property of symmetry is evidently established and a chess board and can be used to reduce the work that the Backtracking Algorithm requires.
In 8 – Queens Problem, 92 solution set has been obtained as shown in the output of the Python Program. From distinct observation of all the solutions, it is inferred that, only 12 solutions out of 92 are distinct. The remaining solutions can be obtained using the principle of symmetry. Eight different solution set can be formed from each set of distinct solution because a chess board can be rotated in 4 ways (90°) each and similarly, a chess board can be reflected in 2 different reflection in each rotated orientation, resulting in a formation of a total of 8 distinct orientations by using the principle of symmetry. However, there is one particular solution out of the 12 distinct solutions in which only 2 rotation is possible. This is because, a rotation of 180° gives the same solution as that of the initial orientation. Thus, only 4 possible orientations are possible for one set of data. Thus, a total of 92 solution set is possible for 8 – Queens Problem.
Lastly, the effectiveness of 4 – queens problem and 8 – queens problem as a lock or combination of any safe (locker) is studied in this IA. Using the concepts of permutation and probability, it has been justified that, if any individual tries to crack the secret key of any safe which is encrypted by a 4 – queens problem, then the probability of getting the correct solution by attempting random orientation will be 1.098×10-3. The same of 8 – queens problem is even more secured with a probability of cracking the orientation is 2.078×10-8. Thus, we can conclude that the 4 – queens’ problem or 8 – queens problem is very difficult to crack with a probability of cracking at a random being approximately equal to zero.
Bibliography
- https://images.app.goo.gl/S6LWabM3BpLgSsXt5
- https://www.fide.com/
- Ruiz, Rubén, and Thomas Stützle. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem." European Journal of Operational Research 177.3 (2007): 2033-2049.
- Schmidt, Douglas C., and Larry E. Druffel. "A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices." Journal of the ACM (JACM) 23.3 (1976): 433-445.
- Rivin, Igor, Ilan Vardi, and Paul Zimmermann. "The n-queens problem." The American Mathematical Monthly 101.7 (1994): 629-639.
- https://www.mathsisfun.com/combinatorics/combinations-permutations.html
- https://www.python.org/download/releases/3.0/
- https://github.com/sol-prog/N-Queens-Puzzle
- https://www.jetbrains.com/pycharm/