Electric Electric -4 years ago 63
Python Question

Checking diagonally in nqueen

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

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download