Недавно разбирался в старых своих наработках/скриптах и наткнулся на скрипт где решалась задача о ферзях. Собственно это послужило написанию статьи о том как проходили этапы написания его алгоритма. Возможно пригодится начинающим программистам для решения похожих задач (код в примерах написан на java).

Вступление

4 года назад была шумиха по поводу задачи о расположении 1000 ферзей на доске 1000х1000. Дело в том что расположение ферзей так чтобы они не били друг друга на доске является задачей с большим количество итераций и как результат долгой по времени выполнения. Как и многим мне захотелось проверить можно ли её решить за приемлемое время.

Изучение задачи

На картинке расположено 8 ферзей которые не пересекаются по горизонтальной, вертикальной или диагональным линиям.

Надо написать скрипт который будет расставлять на доске ферзей по таким правилам.

Алгоритм нахождения ферзей

Для поиска фигур была выбрана рекурсия.

Описание метода который вызывает сам себя:

• Если переданная клетка пересекается с другими фигурами то возвращаем false

• Если переданная клетка не пересекается ни с кем то:

  • устанавливает флаг на доске в true для этой позиции.

  • Если мы дошли до конца (нету следующего ряда) то возвращаем true.

  • Находит первую клетку в следующем ряду и вызывает сам себя с новой клеткой.

    • Если вернулся false то отправляем следующую клетку из ряда или если не осталось клеток то возвращаем false) Предварительно ставим флаг в false на доске у клетки которую изначально получили.

    • Если вернулся true то возвращаем результат.

Такой метод для досок 8x8, 32x32, 50x50 отрабатывает хоть как то. Но если больше то уходит много времени.

Оптимизация

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

В скрипте добавил два списка с свободными колонками и рядами.
Во время проверки из них генерируется список свободных клеток где ряды отсортированы по возрастанию. Поиск начинается с самого первого ряда.
Идея в том чтобы работать только с свободными клетками и начинать поиск с самого маленького ряда.

После этого результат можно было получить вплоть до 400x400.

Уменьшение возможных комбинаций

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

Обратите внимание на картинку.
Часть ферзей можно расположить заранее на доску в соответствии с правилами.
Нужно лишь начать с второй клетки первого ряда и дальше добавлять новые фигуры по формуле "row+1" и "column+2" Этот алгоритм заполнит половину ферзей на доске, а дальше всё сделает скрипт оптимизации который будет находить ряды с наименьшим числом клеток и устанавливать там фигуры.

Поиск на доске 1000x1000 занял ~4 минуты (на процессоре: Intel Core i5-10400H CPU 2.60GHz).

Поиск на доске 1116x1116 занял ~6 минут.

Сам скрипт можно найти тут