Flowchart and Algorithm for N Queen Problem

[2901 views]

Problem Statement: Place n-queens in n x n chessboard so that no two of them can attack each other i.e no two of them are on the same row, column or diagonal. In this problem backtracking is done to solve the problem. solutions of this problems are expressed in n-tuple.

Flowchart for N Queen problem

Algorithm for N Queen problem

Step 1: Start Step 2: Given n queens, read n from user and let us denote the queen number by k. k=1,2,..,n. Step 3: We start a loop for checking if the k<sup>th</sup> queen can be placed in the respective column of the k<sup>th</sup> row. Step 4: For checking that whether the queen can be placed or not, we check if the previous queens are not in diagonal or in same row with it. Step 5: If the queen cannot be placed backtracking is done to the previous queens until a feasible solution is not found. Step 6: Repeat the steps 3-5 until all the queens are placed. Step 7: The column numbers of the queens are stored in an array and printed as a n-tuple solution Step 8: Stop

Explanation:

In the above algorithm,

For the n queen problem we take input of n, lets say n=4 so, k=1,2,3,4.
For placing the first queen i.e k=1,we start a loop for n columns i.e n=4 so till the fourth column.
The first queen can be placed at first column only.
Then we move for the second queen and place it seeing that the first queen is not in the same column or in diagonal with the second queen.
Similarly, the third queen and the fourth queen are placed. But if the fourth queen cannot be placed as it lies in same column or is in diagonal with other queens then back-tracking is done to the previous queens in order of 3,2,1 to achieve the unique feasible solution.
For an n problem queen the same way all the n queens are placed and if the n^th cannot be placed back-tracking is done and the queens are re-ordered and solution is obtained.