Mathematics AA HL
Sample Internal Assessment
5/7
1,973 Words
English
Free

Investigation on N – queen’s problem using backtracking algorithm

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?

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

• 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.

Figure 1 - Chess Board With All The Elements Of Chess

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}$$

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

• 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.

Figure 2 - In This Particular Problem, The Chess Board Comprises Two Rows And Two Columns

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

Figure 3 - A Queen Should Be Placed In First Row And First Column.
Figure 4 - Another Queen Should Be Placed In Second Row In First Available Column.

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

Figure 5 - Step (v) Of The Rules Of Backtracking Algorithm As Mentioned In The Introduction Should Be Followed.
Figure 6 - Another Queen Should Be Placed In Second Row In First Available Column.

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.

Figure 7 - 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:

Figure 8 - A Queen Should Be Placed In First Row And First Column.
Figure 9 - Another Queen Should Be Placed In Second Row In First Available Column.
Figure 10 - Another Queen Should Be Placed In Third Row In First Available Column.

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

Figure 11 - Step (v) Of The Rules Of Backtracking Algorithm As Mentioned In The Introduction Should Be Followed.

No block is available.

Figure 12 - Step (vi) Of The Rules Of Backtracking Algorithm As Mentioned In The Introduction Should Be Followed.
Figure 13 - Another Queen Should Be Placed In Second Row In First Available Column.

No block is available.

Figure 14 - Step (vi) Of The Rules Of Backtracking Algorithm As Mentioned In The Introduction Should Be Followed.
Figure 15 - Another Queen Should Be Placed In Second Row In First Available Column.
Figure 16 - Another Queen Should Be Placed In Third Row In First Available Column

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

Figure 17 - Step (v) Of The Rules Of Backtracking Algorithm As Mentioned In The Introduction Should Be Followed.

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.

Figure 18 - 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:

Figure 19 - A Queen Should Be Placed In First Row And First Column.
Figure 20 - A Queen Should Be Placed In Second Row In First Available Column.
Figure 21 - A Queen Should Be Placed In Third Row In First Available Column.

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

Figure 22 - Step (v) Mentioned In The Rules Of Backtracking Algorithm Should Be Followed As Mentioned In Introduction.
Figure 23 - A Queen Should Be Placed In Third Row In First Available Column.
Figure 24 - A Queen Should Be Placed In Fourth Row In First Available Column.

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

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

Video Course

• Figure 25 - Step (v) Mentioned In The Rules Of Backtracking Algorithm Should Be Followed As Mentioned In Introduction.

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

Figure 26 - Step (vi) Mentioned In The Rules Of Backtracking Algorithm Should Be Followed As Mentioned In Introduction.

As a queen is already placed in the last column, thus again Step (vi) should be followed:

Figure 27 - Step (vi) Mentioned In The Rules Of Backtracking Algorithm Should Be Followed As Mentioned In Introduction.
Figure 28 - Another Queen Should Be Placed In Second Row In First Available Column.
Figure 29 - Another Queen Should Be Placed In Third Row In First Available Column.
Figure 30 - Another Queen Should Be Placed In Fourth Row In First Available Column.
Figure 31 - The obtained solution is shown below:

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:

Figure 32 - 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.

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

• 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:

def _init_(self, size):

        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.

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

Video Course

• Figure 33 -
Figure 34 -
Figure 35 -
Figure 36 -
Figure 37 -
Figure 38 -
Figure 39 -
Figure 40 - Screenshot Of The Output Of The Code

There are 92 solutions of this problem.

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

• 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}$$

• Ilan Grapel

Tech & Law Grad Educator: Boost IB Math/CS Skills with Real-World Projects & Expertise!

• 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.

Figure 41 - This Is The Particular Solution In Which 180° Rotation Is Not Possible As It Is Shown Below:
Figure 42 - queens problem as a lock or combination of any safe (locker) is studied in this IA.

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