Checking diagonally in nqueen

Question

I have a fragment of my code where i wrote functions to check rows, column and diagonal for the queen placement so that they will not attack each other. Currently I'm having issues with the diagonal function:

def checkDiagonal(T):
for i in range(len(T) - 1):
    if abs(T[i] - T[i + 1]) == 1:
        return False
return True

The problem with this function is that it will only consider when queens are one length apart but not when cases more than one.

Example, if N = 7 it prints:

Enter the value of N: 7
0 Q 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 X 0 0 0 0 
0 0 X 0 0 0 0 
0 0 X 0 0 0 0 
0 0 X 0 0 0 0 
Q 0 0 0 0 0 0

the Q in the output is the partial solution i set in the code. The X is the next possible position for the queen but there is one X in the output that is clearly diagonal to the queen and will be attacked.

Partial solution list = [6,0], in this case it will be passed to the function as T

And how do you know what X position you are testing? Or do you want to test them all? In that case N would be good to have. — JohanL

FlorianK FlorianK · Accepted Answer · 2017-05-20T07:39:49

Two points (x1, y1) and (x2, y2) are one the same lower left -> upper right diagonal if and only if y1 - x1 == y2 - x2. If I understand you question correctly, the partial solution T = [0,6] would represent the partial solution [(0,0), (1,6)]. So, since 0 - 0 = 0 != 5 == 6 - 1 , these two elements are not on the same diagonal.

However, for the partial solution [0 , 6, 2] = [(0,0), (1,6), (2,2)] we would have 0 - 0 == 0 == 2 - 2 and hence the two points would be on the same lower left -> upper right diagonal.

For the upper left -> lower right diagonal you would then have to find a similar condition, which I think you should be able to figure out, but let me know if you don't manage to find it.

This would lead to something like the code (only for this diagonal):

def checkDiagonal(T):
    for i in xrange(len(T) - 1):
        for j in xrange(i + 1, len(T))
            if ((T[i] - i == T[j] - j):
                return false
    return true

Be careful however that I didn't have time to test this, so there might be small errors in it, but the general idea should be right.

Checking diagonally in nqueen

1 Answers