Задача N-Queen - это классическая задача в области искусственного интеллекта, где мы пытаемся найти конфигурацию шахматной доски, в которой на доске N × N будет N ферзей, не атакующих друг друга.

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

Несколько замечаний:

  1. Для простоты мы будем использовать массив из индекса 1 (поскольку мы пронумеровали строки и столбцы от 1 до N). Индекс 0 не используется.
  2. Приведен простой код (идея) C ++. Если вы понимаете подход, вы всегда можете написать более гибкую программу с динамическим распределением памяти и так далее.
  3. Ссылку на реализацию Python можно найти в конце статьи.

Определение проблемы. Мы будем описывать конфигурацию платы как одномерный массив. Индексы будут указывать номера столбцов, а значения в соответствующих индексах будут указывать номер строки ферзя в этом конкретном столбце.

Например, {3, 4, 3, 2} соответствует этой конфигурации платы (изображение ниже):

Зачем так определять? Потому что в каждом столбце размещать более одного ферзя не имеет смысла, они просто атакуют друг друга, что не помогает в решении проблемы. А определение как одномерного массива экономит много места.

Создание конфигурации платы займет O (N) времени, предполагая, что мы генерируем случайное значение от 1 до N за O (1).

Проверка конфликтов (наивный): мы можем использовать вложенный цикл для подсчета количества конфликтов, таким образом, для каждой ферзя проверять все следующие ферзя и подсчитывать, сколько там конфликтов, и добавлять это привести. Конфликт возникает, когда:

  1. Ферзи находятся в одном ряду (номера рядов у обоих ферзей одинаковы).
  2. Ферзи находятся в одном столбце (номера столбцов у обоих ферзей одинаковы, в нашем определении проблемы этого не произойдет).
  3. Обе ферзи находятся на одной диагонали (абсолютная разница в строках равна абсолютной разнице в столбцах).

Этот подход занимает O (n²).

Достижение линейной временной сложности: мы будем использовать пространство O (N), чтобы достичь линейной временной сложности при проверке конфликтов.

Вводятся три одномерные таблицы (или массивы). Один для хранения частоты ферзей в каждом ряду. Один для хранения частоты ферзей в главных диагоналях, а другой - для второстепенных диагоналей.

Проверьте следующее изображение доски для индексации строк и столбцов для нашего определения проблемы.

Теперь мы знаем, что есть N строк, поэтому размер массива частот строк будет N (или N + 1, поскольку индекс 0 не используется). Объявим его как f_row [], где изначально все индексы будут содержать ноль (0).

Обозначим наш массив конфигурации шахматной доски как Queen []. Мы можем заполнить f_row [] следующим образом:

for (int i = 1; i <= N; i++){
    int val = Queen[i];
    f_row[val]++;
}

Для каждого значения строки мы увеличиваем соответствующий индекс в f_row [] на 1. Довольно просто! Как теперь проверять конфликты? Предположим, ферзь одного ряда не влияет на ферзей другого ряда (они влияют, если они находятся на одной диагонали, но пока не будем это рассматривать). Таким образом, если конфликты являются взаимоисключающими, мы можем отдельно вычислить конфликты для каждой строки и просто добавить их, чтобы получить общие горизонтальные конфликты, нет необходимости проверять перекрытие.

Рассмотрим ситуацию, когда 4 ферзя находятся в одном ряду, а конфликтующие пары соединены красными линиями.

Линии или ребра неориентированы, мы не проверяем обратных конфликтов, т.е. если королева A атакует королеву B, королева B также атакует королеву A, но мы рассматриваем это как единичный конфликт.

Мы можем наблюдать, что все конфликтующие ферзя в одном ряду фактически образуют «полный график», таким образом, каждый ферзь связан с каждым другим ферзем. А количество граней - это количество конфликтов. Формула для проверки количества ребер в полном графе, где есть N узлов:

(N * (N-1)) / 2

Важно отметить, что это наблюдение также применимо, когда мы будем проверять диагонали.

В нашем примере с 4 ферзями общий конфликт в этой строке = (4 * (4–1)) / 2 = 6.

У нас есть частота строк, хранящаяся в f_row []. Чтобы вычислить общее количество горизонтальных конфликтов, мы можем использовать этот подход:

for (int i = 1; i <= N; i++){
    int queens = f_row[i];
    result += ((queens * (queens - 1) / 2);
}

Чтобы проверить наличие диагональных конфликтов, нам нужно немного по-другому наблюдать за доской. Сначала попробуем основные диагонали. См. Следующий рисунок, на котором каждая ячейка доски содержит сумму значений строки и столбца.

Если вы присмотритесь, вы увидите, что все (главные) диагонали имеют одинаковое суммарное значение. То есть, если ферзь A стоит на позиции со значением 10, а королева B также где-то со значением 10, возникает конфликт!

Как и строки, мы также будем использовать частотную таблицу. Но на этот раз в два раза больше. Поскольку максимальное суммарное значение, которое мы можем иметь, является суммой самой высокой строки и самого высокого столбца, N + N. Обозначим это как f_mdiag [] (здесь mdiag относится к главной диагонали).

Мы можем заполнить его так:

for (int i = 1; i <= N; i++){
    int row = Queen[i];
    int sum = row + i; // i is column value
    f_mdiag[sum]++;
}

Для вторичных диагоналей мы должны перевернуть индексирование столбца (или строки, но не обоих). Теперь просуммируйте значения строки и столбца для каждой ячейки и наблюдайте.

Опять же, диагонали, которые мы ищем, имеют одинаковые значения суммы. Итак, нам нужна другая таблица частот, такого же размера, как и предыдущая.

Заполнение можно сделать так:

for (int i = 1; i <= N; i++){
    int row = Queen[i];
    int sum = (N - row + 1) + i; // flipping is done by N - row + 1
    f_sdiag[sum]++;
}

Теперь мы можем перебирать оба этих массива и использовать (N * (N-1)) / 2, чтобы сгенерировать количество конфликтов на каждой диагонали и добавить их к результату. Примерно так (для f_mdiag []):

for (int i = 1; i <= (N+N); i++){ // note here, N+N, not N
    int queens = f_mdiag[i];
    result += ((queens * (queens - 1))/2);
}

На самом деле, как мы вычисляли конфликты, все настройки исключают друг друга. Главные диагональные конфликты не влияют на вычисление вторичных диагональных конфликтов или конфликтов строк и наоборот - даже если один и тот же ферзь может рассматриваться один раз как член строки, а затем как диагональный член. Таким образом, мы можем обновить все частоты (строки, основные и второстепенные диагонали) в одном цикле (даже во время генерации конфигурации платы!), А также вычислить результат в другом цикле.

Проверьте это, например:

for (int i=1; i<=N; i++){
    Queen[i] = generate_random(1, N); // generating queen position 
    int val = Queen[i];
    f_row[val]++;               // updating frequency of rows
    f_mdiag[val + i]++;         // and main diagonals
    f_sdiag[N - val + 1 + i]++; // and secondary diagonals
}
int result = 0;
for (int i=1; i<=(N+N); i++){ // this loop runs from 1 to N+N
    int x = 0, y = 0, z = 0;
    if (i <= N) x = f_row[i];  //number of queens in ith row
    y = f_mdiag[i];   //number of queens in ith main diagonal
    z = f_sdiag[i];   //number of queens in ith secondary diagonal
    result += (x * (x - 1)) / 2; // adding to result
    result += (y * (y - 1)) / 2;
    result += (z * (z - 1)) / 2;
}

При таком подходе временная сложность составляет O (N). Сложность пространства также O (N).

Проверьте Python code для этого подхода.

Надеюсь, это вам поможет!

Позвольте мне знать ваши мысли :)