По диагонали проверьте королеву JAVA

Question

У меня проблема с пониманием кода, который я получил в Интернете. Это проверка королевы, если есть столкновение с другими королевами. Может кто-нибудь объяснить мне, что это делает? Первое условие, я знал, что это проверка той же строки, но как насчет абсолютного числа?

if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) 
{
     return false;
}

Вот полный код:

class NQueen {

private int[] board;
private int size;
private ArrayList allSolutions = null;

public int[] getBoard() {
    return board;
}
public ArrayList getAllSolutions() {
    return this.allSolutions;
}
public NQueen(int size) {
    this.size = size;
    board = new int[this.size];
    this.allSolutions = new ArrayList();
}
public void place(int row) {
            // base case
    if (row == size) {
        int[] temp = new int[size];
                    // copy in temp array
        System.arraycopy(board, 0, temp, 0, size);
                    // add to the list of solution
        allSolutions.add(new Solution(temp));
        return ;
    } else {
        for (int i = 0; i < size; i++) {

            board[row] = i;
                            /* when you place a new queen
                             * check if the row you add it in, isn't 
                             * already in the array. since the value of arrray is
                             * the row, so we only need to check the diagonals no need to check for collisions on the left or right. 
                             * As long as there is no duplicate values in the array.*/
            if (valid(row)){
                               place(row + 1);
                            }

        }
    }
}
public boolean valid(int row) {
    for (int i = 0; i < row; i++) {
                    // if same row  or same diagonal
        if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) 
                    {
                        return false;
        }
    }
    return true;
}

}

Answer 1

Если у вас есть двумерный массив и каждая позиция на доске "ячейка" в массиве, то для того, чтобы быть на одной диагонали, кусок должен иметь одинаковое горизонтальное и вертикальное расстояние.

Math.abs(board[row] - board[i]) == (row - i)

Проверяет именно это. Math.abs - потому что второй кусок может быть верхним левым, верхним правым, нижним правым и нижним левым. Не уверен, как именно реализован ваш алгоритм, но, вероятно, неплохо взять и абсолютное значение второго операнда.

Пример с небольшой доской:

  1 2 3 4
1
2 x
3
4     y

Итак, здесь мы иметь горизонтальное расстояние 2 (абс (1-3)) и вертикальное расстояние также 2 (абс (2-4))

Пример 2:

  1 2 3 4
1       x
2     y
3 
4 

Здесь мы имеем только горизонтальное и вертикальное расстояние только 1 (abs (4-3) и abs (1-2))

Follow

Ваш массив хранит в каждом элементе положение ферзя в этом строка. Так что это всего лишь одномерный массив (а не двухмерный, как я изначально предложил).

Так что для моего первого примера ваш массив будет содержать:

[ 0, 1, 0, 3 ]

(я думаю, что код из OP предполагает позиции на основе 0, но инициализирует элементы массива с помощью 0 (new int[size]). Это может быть ошибкой , поскольку 0 является допустимой позицией и может конфликтовать с другими ограничениями, т.е. вы не сможет поместить ферзь в индекс 1, если ферзь из предыдущей или следующей строки неинициализирована (= позиция 0).)

Вернуться к примеру (использование индексов на основе 1 для ясности и во избежание ошибка, упомянутая выше): a[2] - a[4] == 1 - 3 (a[2] == 1, a[4] == 3)

Если вместо элемента "y" перенести в столбец 2, вы получите a[2] - a[4] != 1 - 3, потому что они не делятся диагональ (a[2] == 1, a[4] == 3)