Кратчайший путь коня между двумя полями на шахматной доске, количество и имена битых полей

27.06.23

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

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

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

Наименование Файл Версия Размер
Шахматное поле
.epf 390,26Kb
2
.epf 1.01 390,26Kb 2 Скачать

Перед запуском обработки необходимо указать размерность шахматной доски.

Далее, кликая по нужным полям, расставить фигуры.

Для вычисления пути необходимо отметить поле с конем и пустое поле. Отметка доступна из выпадающего меню по клику на поле. Отмеченные поля выделятся синей рамкой. По окончании отметки двух полей производится расчет минимальных ходов.

Во всех битых выделенным конем полях проставляется символ "Х". Все поля, участвующие в минимальных ходах, выделяются крассным.

Разрешена размерность шахматной доски от 8х8 до 16х16. Размерность ограничена, чтобы не "лопнул" на вычислениях ваш компьютер.

Ход конём

См. также

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

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

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

1 стартмани

30.01.2024    1753    stopa85    12    

33

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

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

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

19.10.2023    4415    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7450    4    SpaceOfMyHead    17    

56

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

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

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

1 стартмани

21.03.2022    7848    7    kalyaka    11    

44

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

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

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

16.12.2021    4443    fishca    13    

36

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

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

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

12.10.2021    8830    John_d    73    

46

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

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

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

31.08.2021    7796    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. ildarovich 7850 23.11.15 13:17 Сейчас в теме
В статье Минимализмы в разделе 14 решается та же задача. Решение заняло 30 строк. Его можно обобщить и на произвольный размер доски и на учет занятых клеток. Там используется алгоритм, который точно не позволит "лопнуть" компьютеру на вычислениях. А сколько строк в предлагаемом решении? И насколько быстро оно работает? Возможность лопания компьютера настораживает.
3. m..adm 255 23.11.15 14:18 Сейчас в теме
(1) ildarovich,
Обработка на 420 строк.
Для расчета ходов используется 110 строк кода (с операторами вывода сообщений, оформление полей и пр.)
"Лопнуть" - имеется ввиду, что при больших размерах доски и определенном размещении фигур, длинна минимального хода может быть очень большая и количество таких ходов может быть десятки тысяч. Для выдачи такой информации и обработки, как ни-крути, надо ресурс компьютера. Поэтому так написано.
Насколько быстро работает - это субъективно.
Т.к. комбинации диктуют длительность механизма вычисления. Грубо говоря, для полей размерностью 8х8 - 10х10 это доли, секунд не зависимо от размещенных фигур.

4. Шёпот теней 1779 24.11.15 08:11 Сейчас в теме
(3) на вашем месте я бы прислушался к ildarovich ...

будет хорошим результатом если снизить количество строк в программе в два раза и/или во столько же раз повысить быстродействие ... задачи очень сложные и очень интересные - если конечно задаться принципом "ограниченных ресурсов" .

... вот ...
5. jan27 732 24.11.15 09:49 Сейчас в теме
(1) раздел 12, если быть точным :)
2. herfis 498 23.11.15 13:52 Сейчас в теме
Ну, в принципе, если нужна готовая визуализация шахматной доски, то 2 стартмани не жалко. Выглядит симпатично.
Только аудитория не шибко широкая выходит для платной публикации и название не сильно подходящее :)
Оставьте свое сообщение