gifts2017

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

Опубликовал Валерий (scientes) в раздел Программирование - Теория программирования

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

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

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

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

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

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

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

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

См. также

Подписаться Добавить вознаграждение

Комментарии

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