How does n-queens isValid check work?

#1

It is a really succinct but mysterious piece of code. I understand the diff == 0 part, but the diff == rowID - i, I do not understand at all? How did they come up with this?

0 Likes
#2

the diff == 0 condition checks if both queens occupy the same column
the diff == row - i checks if they are on the same diagonal.

Just draw a 4x4 matrix and try to understand when 2 queens are on the same diagonal. There are 2 cases: newly added queen is to the left or to the right of the queen we check against.

2 Likes
#3

It still doesn’t make too much sense, but its ok. I found that an easier way to check the diagonals is to see that for a given diagonal, either i +j = constant or i - j = constant where i and j are the row and column of a given cell in a given diagonal. The absolute value and diff were too hard for me to remember/reason about. THANKS

0 Likes
#4

Hi, I would also like to understand an easier approach to determine the validity of placements. Could you provide me code chunk or point me to the resource to understand please? I appreciate it.

0 Likes
#5

I used the leetcode solutions to understand the i+j = constant and i-j = constant, I never understood the EPI way

0 Likes
#6

I understood the EPI way. I used different variable names than given in EPI for better understanding.

private static boolean isValid(List<Integer> colPositions) {
     Integer last = colPositions.size() - 1;
     for (int i = 0; i < last; i++) {
        int diff = Math.abs(colPositions.get(last) - colPositions.get(i));
        boolean inSameDiagonal = (diff == (last - i));
        if (diff == 0 || inSameDiagonal) {
            return false;
        }
     }
     return true;
}
0 Likes