n - Queen's problem�

• The n – queen problem is the generalized problem of 8-queens or 4-queens problem. Here, the n – queens are placed on a n * n chess board, which means that the chessboard has n rows and n columns and the n queens are placed on thus n * n chessboard such that no two queens are placed in the same row or in the same column or in same diagonal. So that, no two queens attack each other.

Amity School of Engineering & Technology

• Here, we suppose that the queen i is to be placed in row i. We can say that 1 queen is placed in the first row only but can have columns from 1, 2... n so that they satisfy all the explicit and implicit constraints.
• All solutions to the n – queen’s problem can be therefore represented as n – tuples (x1, x2... xn) where xi is the column on which queen i is to be placed.

​

Amity School of Engineering & Technology

Algorithm N Queen (k, n)

// Using backtracking, this procedure prints all possible placements of

// n- queens on the n*n chess board so that they are non-attacking.

{

for i = 1 to n do

{

if (Place (k, i))then

{

X[k] = i;

if (k = =n) then write (x[1: n ]) ;

else N Queens (k+1, n); } } }

Amity School of Engineering & Technology

Algorithm Place(k,i)

{

for(j=1 to k-1 do

if((x[ j]==i) || (ABS(x[ j]-i)==ABS(j-k)))

then return false;

return true;

}

Amity School of Engineering & Technology

4 - Queen's problem�

• In 4- queens problem, we have 4 queens to be placed on a 4*4 chessboard, satisfying the constraint that no two queens should be in the same row, same column, or in same diagonal.

Amity School of Engineering & Technology

​

​

​

​

​

​

• so the desired result for 4 queens is {2, 4, 1, 3}

Amity School of Engineering & Technology

• One possible solution for 8 queens problem is shown in fig:

Thus, the solution for 8 -queen problem is (4, 6, 8, 2, 7, 1, 3, 5).  

Amity School of Engineering & Technology