Головоломки > Программы симуляторы головоломок
Программы для решения головоломок, Filler3d
kosshams:
Я (Шамсутдинов Константин) написал несколько программ для решений головоломок, большая часть из которых выложена на моем сайте: http://kosshams.ru/ . Программу Filler3d для 2-x и 3-x мерного заполнения выкладываю тут в последней версии - гораздо более продвинутой, чем на моем сайте: http://kosshams.ru/Files/Filler3d/Filler3d.exe
Вот скриншот с решением в программе задачи составления куба 7x7x7 из 27 деталей. На это ушло 3 дня вычислений на 8 компьютерах по три приложения на каждом.
Программа Filler3d покрывает много видов задач замощения и некоторых других, см. ее описание по кнопке "?". Не реализован случай клетки в виде диагонального деления куба.
Я писал некоторым людям о своих идеях по поводу использования этой программы. Но пообщавшись на тему производства головоломок понял, что мои идеи немного не соответствуют реальной жизни. Сейчас я видимо исчерпал свой лимит времени на написание программ, связанных с головоломками.
Начал программу с кубиком Рубика, пока она рассчитывает комбинации до 13 ходов, разобрался с алгоритмами Коцембы и даже придумал небольшое усовершенствование. Но эти алгоритмы потребуют много усилий и времени на реализацию.
Могу делиться идеями и наработками, связанными с решением головоломок. Думаю, что хорошо разбираюсь в алгоритмах перебора вариантов. Несколько идей алгоритмов для решения разных задач я так и не воплотил. Могу поделиться формулировками этих задач.
Philipp:
Очень рад видеть Вас на нашем форуме.
Я не большой специалист в не шарнирных головоломках и есть пара вопросов по Вашей программе.
Учитывает ли она при подборе вариантов деталей факт практической собираемости головоломки, сам процесс и вариантность процесса сборки?
Каковы лучшие достижения в подобного вида головоломках без участия Вашей программы?
На фото виден изготовленный образец. Какова его история?
Мне понятна реакция производителей головоломок, но Ваша деятельность представляет огромный интерес для мирового головоломочного сообщества.
Что касается Кубика Рубика 3х3х3, здесь конечно тема изучена достаточно подробно, но существует масса направлений в шарнирных головоломках, для которых давно назрела необходимость математического моделирования. Это как генерация новых головоломок по заданным параметрам осей вращения и слоёв, так и создание очень интересных модификаций, например в виде бандажей (ограничение вращений). Последние имеют большие перспективы, так как мало изучены до сих пор и представляют пик сложности решения среди всех шарнирных головоломок.
Plut`on:
Константин, приветствую!
Как раз на днях заходил на ваш сайт.
Как я понял, он давно не обновлялся, по крайней мере я не нашёл там программ о которых вы рассказывали на последней встрече Диогеновцев.
Может быть вы перенесёте в эту ветку все свои программы, уже представленные на сайте и новые?
kosshams:
Эту китайскую головоломку с деталями 6 цветов, из которых нужно собрать два куба 7x7x7, в каждом из которых детали 3 цветов, мне подарил мой знакомый (Влад), узнав, что я сделал эту программу. Вот упаковка этой головоломки:
Сейчас сайт, который там указан 52mopin.com не существует - вероятно, домен перестали оплачивать.
Первый куб Влад собрал, используя картинку трех граней, которая была выложена в интернете. Для этого он написал программу. Процесс сборки, зная расположение деталей потребовал от него усилий. Три детали, которые задвигаются последними он пометил ручкой цифрами 1, 2, 3 (левый куб на фото). Второй куб просчитать в своей программе он не смог.
В свою программу я добавил функцию "Часть вариантов" (см. описание), которая позволяет перебор разбить на части и запустить в разных приложениях, что я и сделал на своей работе. Деталь 7x1x1 можно расположить 10 несимметричными способам в этом кубе, причем в некоторых из этих способов остается симметрия поля. Моя программа не учитывает симметрию после установки на поле фигурок, но учитывает в симметрию поля, поэтому, чтобы сократить время вычислений я разбил задачу на 10 задач, где эта палка исключена из условия и из поля. Замечу, что решение, когда палка располагается на ребре маловероятно, так как она будет выпадать.
Получилось 3 решения: http://kosshams.ru/Programs/Filler3D/Solutions.zip. В файле "Решение2 (инструкция в тексте)" содержится последовательность сборки (кнопка "Т"). Правда инструкцию я написал не совсем аккуратно, но хоть как-то.
Решения отличаются расположением 3 или 4 деталей, которые во всех случаях занимают один и тот же объем. Наверное, все три можно собрать. Сборка у меня заняла несколько часов. Я использовал возможность трехмерного показа подмножества фигурок:
Видно, что в решении часть внутренних плоскостей гладкие, что могло бы быть подсказкой при нахождении решения человеком. Некоторые фигурки объединяются по 2 или 3 штуки и как целое вставляются. В программе нет возможности выявления подмножества фигурок, которые можно подвинуть. Алгоритмически эта задача проста и не требует долгого перебора вариантов. Вручную найти это подмножество в программе при большом количестве фигурок может быть непросто. Если фигурки при вставлении требуют сложных маневров (в этой задаче такого нет), то, конечно, требуется перебор вариантов. С другими программами я не знаком, хотя Красноухов В.И. упоминал 3dSolver, которым пользуются его зарубежные коллеги. На вопросы по задаче заполнения я, наверное, ответил.
kosshams:
Хорошо я выложу эти программы в этой теме (и отвечу по кубику Рубика) - постараюсь сегодня или завтра. Домен narod перешел ucoz и стало еще более неудобно пользоваться сайтом. Я начал размещать на myjino, где заплатил минимальную плату 33 руб/мес. за полгода. Следующая ссылка будет офтопиком: http://kosshams.myjino.ru/
Навигация
Перейти к полной версии