N queens problem

N Queens Problem


Created by:
Shridhar Shah


Class- 3CEB
Subject- Mathematical Foundation for Computer Science
























Abstract -

N Queens Problem is a classical puzzle of placing mutually non-attacking N queens on N x N board and is very popular among researchers. This problem has become very useful in the recent past for the scientists because of having many applications in the real world. In this paper we propose this as a game and implement systematic search methods to get to the solution. Main focus of this problem is to make a computer learn from human activities during the game playing and use them in artificial intelligence.

Keywords –
N is the no. of queens placed in NxN chessboard ,for e.g. 8 queens in 8x8 chessboard(Normal chessboard), Backtracking -is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate 'p' ("backtracks") as soon as it determines that 'p' cannot possibly be completed to a valid solution.
Introduction
The puzzle was originally proposed in 1848 by the chess player Max Bezzel, and over the years, many mathematicians, including Gauss, have worked on this puzzle and its generalized n-queens problem.
The first solution for 8 queens was provided by Franz Nauck in 1850. Nauck also extended the puzzle to n-queens problem (on an n×n board—a chessboard of arbitrary size).
In 1874, S. Gunther proposed a method of finding solutions by using determinants, and J.W.L. Glaisher refined this approach.
Edsger Dijkstra used this problem in 1972 to illustrate the power of what he called structured programming.







The 8 queen problem is a case of more general set of problems namely "N queen problem". The basic idea: How to place n queen on n by n board, so that they don't attack each other(in first move). As we can expect the complexity of solving the problem increases with n. The solution of this problem can be obtained by Backtracking algorithm. For e.g.- for an 8x8 chessboard 8 queens can placed in total 92 ways so that none of them can threaten each other, till date no general or well defined formula is found which can find no. of ways for NxN chessboard so that no queen threatens/attacks each other.
It is unsolved problem in the field of computer science and continuous research is taking place for this problem.

Motivation
As we are in the field of computer science, N queens problem has great application in the field of artificial intelligence, parallel memory storage schemes, VLSI testing, traffic control, and deadlock prevention .So N queens problem having great application in the field of computer science we should study the problem and it's efficient algorithm.

Literature Survey
Statement:-"To find no. of possible solutions of placing N queens on NxN chessboard such that no queen attack/threaten each other."
For finding solution of N queens problem i.e. placing queens on the chessboard in such a manner that no queen attacks each other we take the most generalized case : 4x4 chessboard or regular 8x8 chessboard .
For an 8x8 chessboard the first possible method is by brute force technique;blindly trying to place eight queens on every possible location which is next to impossible as we have to check 64!/56! =178,462,987,637,760 possible placements.
From the statement of N queens problem we can deduce that the solution requires no two queens sharing the same row, column, or diagonal.

Backtracking method:
1) Put the first queen in the first row and first column.
2) Put the second queen in the first row and second column ;if it attacks the first queen ,then backtrack(empty) the first row in second column, move the second queen in next row in second column until it does not attacks the first queen.
3) Put the third queen in the first row and third column ;if it attacks the first queen/second queen ,then backtrack(empty) that position, move the third queen in next row in third column until it does not attacks the first queen/second queen .If the third queen attacks either first or second queen in all rows of corresponding places then we have to backtrack(empty) the queens from their place.
4) Repeat the steps from 1 to 3 for pth queen (queen at pth column/position) if it does not attack its previous queen (at (p-1)th position).
5) If any queen at pth position attacks its previous or queens at earlier row ,then we have to empty the corresponding previous queen.
It will be clear from example:
(4x4 chessboard)



By applying the above steps we get,
Q1















Q1
Q2















Q1




Q2










Q1








Q2









A. Yes B. No C. No D. Yes





Q1

Q3






Q2






Q1





Q3


Q2






Q1








Q2
Q3





Q1








Q2




Q3





E. NO F. NO G. NO H. NO

The Q3 attacks all other previous column queens so it could not be the possible solution , hence we have to backtrack(empty/pop) Q3,then Q2 and finally Q1.
Here Q3 is attacking either Q1 or Q2 from its corresponding column so instead of adding Q3 we have to remove Q3 and Q2, this process is called as pruning of queen.






Q1















Q1








Q2
























I. Remove Q3 J. Remove Q2 K. Remove Q1
In steps I,J and K Q3,Q2 and Q2 are removed as it does not solve the problem .
According to the Backtracking procedure we have to put the first queen in second row first column and repeat steps from 1 to 3.





Q1












Q2


Q1















Q1
Q2















Q1




Q2









L. M. No N. No O. No





Q1








Q2




Q3

Q1








Q2




Q3

Q1


Q4





Q2






Q3
Q4
Q1








Q2




P. Yes Q. Yes R. No S. No



Q3

Q1






Q4

Q2





T. Desired solution
From the above step 1-3 we can get our desired solution T such that no queens attack each other.(Multiple solutions possible )
Also we can find the solution for 8 queens problem by the backtracking method and it comes out to be 92 solution out of which 12 are distinct solution(because many solutions are reflection or rotation of each other) .
Observations / Results

We have observed that all queen should be in different row and different columns and different diagonal.
Till date scientists have found solutions up to 26 queens only.
Following are the solutions of the N queen problem(N=1,2,3…..,26)
Order
("N") Total Solutions Unique Solutions
---------------------------------------------------------

1 1 1
2 0 0
3 0 0
4 2 1
5 10 2
6 4 1
7 40 6
8 92 12
9 352 46
10 724 92 11 2,680 341
12 14,200 1,787
13 73,712 9,233
14 365,596 45,752 15 2,279,184 285,053 16 14,772,512 1,846,955 17 95,815,104 11,977,939 18 666,090,624 83,263,591 19 4,968,057,848 621,012,754 20 39,029,188,884 4,878,666,808 21 314,666,222,712 39,333,324,973 22 2,691,008,701,644 336,376,244,042 23 24,233,937,684,440 3,029,242,658,210 24 227,514,171,973,736 28,439,272,956,934 25 2,207,893,435,808,352 275,986,683,743,434 26 22,317,699,616,364,044 2,789,712,466,510,289

From the table it can be deduced that no solution exist for two and three queens problem.
As the value of Queens i.e. N increases, the total no. of solution increases hugely (after 7 queens).
N queens problem can be solved only backtracking and not by brute force method as it gives the proper solution of the problem.
Considering the case of 8x8 chessboard, performing the required calculations and applying we see that we get 92 solutions. But on viewing all the solutions carefully, we realize that not all are unique. Only 12 solutions out of 92 are unique. Else all are reflection or rotation of one another.
Moreover, there is no generic formula for finding number of solutions for a given N. But, a suitable algorithm can be developed to find the solution.

Conclusion
Using the concept of Backtracking, the major advantage was the ability to find and count the possible solutions rather than just one while offering decent speed. 
Finding it's applications in branches like Artificial Intelligence, it can be viewed as a very critical method to generate optimum solutions.











References:
http://theory.cs.uvic.ca/amof/e_queeI.htm
http://www.researchgate.net/publication/258921846_A_Novel_Approach_to_8-Queen_Problem_Employing_Machine_Learning
Table from- http://www.datagenetics.com/blog/august42012/
https://youtu.be/JkP-xats3no