Задачи о 5 и 9 ферзях

12.09.13

Разработка - Математика и алгоритмы

Задача о ферзях-часовых. На шахматной доске надо расставить 5 ферзей, чтобы они держали под боем все клетки доски.
Задача В. Франгена, расставить на шахматной доске 10 “белых” и 9 “чёрных” ферзей так, чтобы ни один из них не находился под ударом противника

Скачать файлы

Наименование Файл Версия Размер
Задача о 5 ферзях
.epf 131,72Kb
1
.epf 1.0.3 131,72Kb 1 Скачать

5 ферзей появились не случайно. Это минимальное количество фигур, при которых задач имеет решение. Как и в задаче о 8 ферзях (//infostart.ru/public/198717/) в решении используется перебор с возвратом. Но есть и дополнительные приемы. Так количество сочетаний вычисляется с помощью метода динамического прграммирования. Кроме этого, используется процедура генерации сочетаний по k из N. При поиске решений предполагается, что фигуры расположены в разных колонках и разных строках. В программе пристутствует возможность найти нужное расположение в ручную. Пользователь может ограничить количество найденных решений, в целях уменьшения времени работы процедуры поиска.

 Эта задача была предложена В. Франгеном в 1980 г. и получила специальный приз на международном шахматном конкурсе. Автор предложил расставить на шахматной доске 10 “белых” и 9 “чёрных” ферзей так, чтобы ни один из них не находился под ударом противника, и считал, что задание выполняется единственным образом .Впоследствие автор задачи нашел еще одно решение, но оказалось, что есть и третье.

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

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

В обработке реализован алгоритм поиска решений задачи о 9 ферзях.

Шахматные задачи

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7460    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8837    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7803    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. scientes 288 04.09.13 10:16 Сейчас в теме
Долго искал в Сети эти самые три решения задачи Франгена. В конце концов нашел. С помощью обработки мне тоже удалось отыскать эти расстановки. Вопрос есть ли еще, пока открыт. Но в ближайшее время закроется.
2. scientes 288 04.09.13 10:34 Сейчас в теме
Полный перебор позволил найти 24 решения. Но уникальных меньше, остальные получаются путем поворота доски.
3. ugroblin 04.09.13 12:47 Сейчас в теме
3 решения. 24 получается поворотом доски - *4 варианта и отражением - *2.
4. scientes 288 04.09.13 14:22 Сейчас в теме
Поскольку все фигуры, которые образуют искомое расположение лежат на одной половине доски, то перебор можно вести только по одной половине. Это резко сокращает время счета. Так для программы в 1С процедура поиска работала 3 мин. Было найдено 6 решений, уникальных, как и предполагалось, 3.
Прикрепленные файлы:
5. пользователь 05.12.19 23:34
Сообщение было скрыто модератором.
...
Оставьте свое сообщение