NQUEEN problem

hii guys,

i am trying to to do N-queen problem in which i have a function Place(k,i) which returns true if a queen can b placed at the K’th row and i’th column but am facing problem in understanding the following algorithm

Place(k,i)
{
for j=1 to k-1 do

     if((x[j]=i) or (abs(x[j]-i)=abs(j-k))

           then return false;


return true;

}

here x is a global array whose k-1 values are set

especially i fail to visualise the same diagonal and same column checking in the if block… :frowning:

2 Likes

See the chess board below, that should help you visualize.

alt text

The blue dot is conflicting with both red dots. For current scenario, various variables are-

x = {1, 3 ...}
i = 3
k = 3

And when j = 1, |x[j] - i| (the vertical line) equals the |j - k| (the horizontal line), hence the 2 queens are on diagonal. Using abs we can take care of both upper and lower diagonal.

3 Likes

@vinayak garg thanx for explaining it so beautifully … got it atlast :slight_smile:

@zargus: Glad to help :slight_smile: