gifts2017

Задачи на шахматной доске

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

Предлагается вариант решения двух классических задач на шахматной доске - это задача о расстановке ферзей и задача о перемещении коня по доске. В последней задаче конь должен обойти все клетки доски, побывав в каждой ячейке только один раз. Варианты решения уже присутствуют на портале. Отличие данной версии - интерфейс. Рисуется доска, отображаются фигуры и перемещения. Плюс для задачи о расстановке ферзей реализован авторский алгоритм, что позволило увеличить скорость поиска решений примерно в три раза.( для доски 11х11 время уменьшилось с 3 мин. 39 сек до 1 мин. 03 сек)

В чем суть авторского решения задачи о расстановке ферзей ? Как и обычно идет перебор  вариантов с отбрасыванием заранее непригодных. То есть фигуры должны располагаться в разных колонках, в разных строках и не лежать на одной диагонали.  Для удаления ненужных полей  шахматная доска разворачивается в одномерный массив и при постановке новой фигуры помечаются (прибавляется единица) ко всем ячейкам, которые находятся под боем. Такой подход оказался продуктивным, что показали замеры скорости выполнения обычного кода и кода с использованием предложенного метода.

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

Наименование Файл Версия Размер Кол. Скачив.
Обработка задачи на шахматной доске
.epf 132,77Kb
23.08.13
7
.epf 1.1 132,77Kb 7 Скачать

См. также

Подписаться Добавить вознаграждение
В этой теме еще нет сообщений.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа