Русский
Русский
English
Статистика
Реклама

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

Недавно разбирался в старых своих наработках/скриптах и наткнулся на скрипт где решалась задача о ферзях. Собственно это послужило написанию статьи о том как проходили этапы написания его алгоритма. Возможно пригодится начинающим программистам для решения похожих задач (код в примерах написан на 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
К списку статей
Опубликовано: 17.05.2021 18:06:47
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Java

Алгоритмы

Ферзи

Задача

Задача о восьми ферзях

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru