One of the oldest chess based puzzles is known, affectionately, as The Eight Queens Problem.
So what is the Eight Queen Problem???
The challenge is to place eight queens on the board such that no queen is attacking any of the others. It is a great puzzle because it is very hard to solve manually because the queen is able to attack any square on the same row, any square on the same column, and also any square on either of the diagonals.
So how to solve the puzzle????
There are many possible algorithms that can be used to find solutions to the eight queen’s problem, and a smaller subset of algorithms that can be used to enumerate all possible solutions.
First of all we should know how many ways we can place 8 queen on a standard 8x8 chess board.
We have 64 total squares and 8 queens to place, so we have 56 squares that will remain blank.
Now using permutation and combination technique we can calculate this .......
if we have 64 objects then 64 objects can be arranged them in 64! ways.
64!= 646332......32*1
Now we have 56 blank squares and so 56! ways we can arrange them. And we also have to consider the queens. There are 8 queen so 8! ways we can arrange them.
So the number of ways we can arrange 8 queens on a standard 8x8 chessboard is
64!/(56!*8!)=4,426,165,368
SO how many solutions are there out of this 4 billion ways you can arrange 8 queens that will no attack each other???
The answer is out of this 4 billion there are only 92 distinct solutions that will no attack each other.
One of the algorithm is .........
A more efficient algorithm (which can be implemented recursively or not) is to start in the first column in the top left, then it then places a queen in the second column and moves it until it finds a place where it cannot be hit by the queen in the first column.
It then places a queen in the third column and moves it until it cannot be hit by either of the first two queens. Then it continues this process with the remaining columns. If there is no place for a queen in the current column the program goes back to the preceding column and moves the queen in that column. If the queen there is at the end of the column it removes that queen as well and goes to the preceding column. If the current column is the last column and a safe place has been found for the last queen, then a solution of the puzzle has been found. If the current column is the first column and its queen is being moved off the board then all possible configurations have been examined, all solutions have been found, and the algorithm terminates.
Check this link if you want to know more details.......
