[Java, Алгоритмы] Алгоритм нахождения 1000 ферзей на шахматной доске

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
17-Май-2021 20:32

Цитировать

Недавно разбирался в старых своих наработках/скриптах и наткнулся на скрипт где решалась задача о ферзях. Собственно это послужило написанию статьи о том как проходили этапы написания его алгоритма. Возможно пригодится начинающим программистам для решения похожих задач (код в примерах написан на 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 минут.Сам скрипт можно найти тут
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_java, #_algoritmy (Алгоритмы), #_ferzi (ферзи), #_zadacha (задача), #_zadacha_o_vosmi_ferzjah (задача о восьми ферзях), #_java, #_algoritmy (
Алгоритмы
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 14:49
Часовой пояс: UTC + 5