Автор Тема: Программы для решения головоломок, Filler3d  (Прочитано 7970 раз)

0 Пользователей и 2 Гостей просматривают эту тему.

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Я (Шамсутдинов Константин) написал несколько программ для решений головоломок, большая часть из которых выложена на моем сайте: http://kosshams.ru/ . Программу Filler3d для 2-x и 3-x мерного заполнения выкладываю тут в последней версии - гораздо более продвинутой, чем на моем сайте: http://kosshams.ru/Files/Filler3d/Filler3d.exe
Вот скриншот с решением в программе задачи составления куба 7x7x7 из 27 деталей. На это ушло 3 дня вычислений на 8 компьютерах по три приложения на каждом.



Программа Filler3d покрывает много видов задач замощения и некоторых других, см. ее описание по кнопке "?". Не реализован случай клетки в виде диагонального деления куба.
Я писал некоторым людям о своих идеях по поводу использования этой программы. Но пообщавшись на тему производства головоломок понял, что мои идеи немного не соответствуют реальной жизни. Сейчас я видимо исчерпал свой лимит времени на написание программ, связанных с головоломками.
Начал программу с кубиком Рубика, пока она рассчитывает комбинации до 13 ходов, разобрался с алгоритмами Коцембы и даже придумал небольшое усовершенствование. Но эти алгоритмы потребуют много усилий и времени на реализацию.
Могу делиться идеями и наработками, связанными с решением головоломок. Думаю, что хорошо разбираюсь в алгоритмах перебора вариантов. Несколько идей алгоритмов для решения разных задач я так и не воплотил. Могу поделиться формулировками этих задач. 
« Последнее редактирование: 03 Марта 2015, 05:25:26 от kosshams »

Оффлайн Philipp

  • Администратор
  • *****
  • Сообщений: 1 962
  • Пол: Мужской
  • С Администратором лучше не спорить.
Re: Программы для решения головоломок, Filler3d
« Ответ #1 : 27 Февраля 2014, 08:49:39 »
Очень рад видеть Вас на нашем форуме.

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

Мне понятна реакция производителей головоломок, но Ваша деятельность представляет огромный интерес для мирового головоломочного сообщества.

Что касается Кубика Рубика 3х3х3, здесь конечно тема изучена достаточно подробно, но существует масса направлений в шарнирных головоломках, для которых давно назрела необходимость математического моделирования. Это как генерация новых головоломок по заданным параметрам осей вращения и слоёв, так и создание очень интересных модификаций, например в виде бандажей (ограничение вращений). Последние имеют большие перспективы, так как мало изучены до сих пор и представляют пик сложности решения среди всех шарнирных головоломок.
« Последнее редактирование: 27 Февраля 2014, 08:51:22 от Philipp »

Оффлайн Plut`on

  • Глобальный модератор
  • *****
  • Сообщений: 1 119
  • Пол: Мужской
  • коллекционер
Re: Программы для решения головоломок, Filler3d
« Ответ #2 : 27 Февраля 2014, 10:56:26 »
Константин, приветствую!

Как раз на днях заходил на ваш сайт.
Как я понял, он давно не обновлялся, по крайней мере я не нашёл там программ о которых вы рассказывали на последней встрече Диогеновцев.

Может быть вы перенесёте в эту ветку все свои программы, уже представленные на сайте и новые?


Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #3 : 27 Февраля 2014, 11:59:35 »
Эту китайскую головоломку с деталями 6 цветов, из которых нужно собрать два куба 7x7x7, в каждом из которых детали 3 цветов, мне подарил мой знакомый (Влад), узнав, что я сделал эту программу. Вот упаковка этой головоломки:

Сейчас сайт, который там указан 52mopin.com не существует - вероятно, домен перестали оплачивать.
Первый куб Влад собрал, используя картинку трех граней, которая была выложена в интернете. Для этого он написал программу. Процесс сборки, зная расположение деталей потребовал от него усилий. Три детали, которые задвигаются последними он пометил ручкой цифрами 1, 2, 3 (левый куб на фото). Второй куб просчитать в своей программе он не смог.
В свою программу я добавил функцию "Часть вариантов" (см. описание), которая позволяет перебор разбить на части и запустить в разных приложениях, что я и сделал на своей работе. Деталь 7x1x1 можно расположить 10 несимметричными способам в этом кубе, причем в некоторых из этих способов остается симметрия поля. Моя программа не учитывает симметрию после установки на поле фигурок, но учитывает в симметрию поля, поэтому, чтобы сократить время вычислений я разбил задачу на 10 задач, где эта палка исключена из условия и из поля. Замечу, что решение, когда палка располагается на ребре маловероятно, так как она будет выпадать.
Получилось 3 решения: http://kosshams.myjino.ru/Filler3d/Solutions.zip. В файле "Решение2 (инструкция в тексте)" содержится последовательность сборки (кнопка "Т"). Правда инструкцию я написал не совсем аккуратно, но хоть как-то.

Решения отличаются расположением 3 или 4 деталей, которые во всех случаях занимают один и тот же объем. Наверное, все три можно собрать. Сборка у меня заняла несколько часов. Я использовал возможность трехмерного показа подмножества фигурок:

Видно, что в решении часть внутренних плоскостей гладкие, что могло бы быть подсказкой при нахождении решения человеком. Некоторые фигурки объединяются по 2 или 3 штуки и как целое вставляются. В программе нет возможности выявления подмножества фигурок, которые можно подвинуть. Алгоритмически эта задача проста и не требует долгого перебора вариантов. Вручную найти это подмножество в программе при большом количестве фигурок может быть непросто. Если фигурки при вставлении требуют сложных маневров (в этой задаче такого нет), то, конечно, требуется перебор вариантов. С другими программами я не знаком, хотя Красноухов В.И. упоминал 3dSolver, которым пользуются его зарубежные коллеги. На вопросы по задаче заполнения я, наверное, ответил.

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #4 : 27 Февраля 2014, 12:05:48 »
Хорошо я выложу эти программы в этой теме (и отвечу по кубику Рубика) - постараюсь сегодня или завтра. Домен narod перешел ucoz и стало еще более неудобно пользоваться сайтом. Я начал размещать на myjino, где заплатил минимальную плату 33 руб/мес. за полгода. Следующая ссылка будет офтопиком: http://kosshams.myjino.ru/

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #5 : 28 Февраля 2014, 00:04:59 »
Думаю, что для забандаженных шарнирных головоломок нужно писать программу для редактирования и перебора вариантов на глубину на сколько хватит памяти. Позицию задавать положением каждого жесткого элемента. Сам я сейчас не буду этим заниматься.
Вот моя программа для кубика Рубика: kosshams.myjino.ru/Programs/Rubik.exe. Описание по кнопке "?". Она считает только до 13 ходов. Обладает возможностью частичного задания позиции. В последнем слое можно задавать только ориентацию кубиков с желтым цветом, не указывая какой это кубик:

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #6 : 10 Марта 2014, 11:17:59 »
Вообще, для забандаженных шарнирных головоломок типа кубика Рубика с большим количеством вариантов (больше, чем у кубика 3x3x3) нужно с помощью программы искать комбинации, а не решение от начала до конца. Комбинацией является последовательность ходов, начиная от какой-то фиксированной конфигурации бандажных соединений, не учитывая раскраску элементов. После этой комбинации ходов конфигурация может стать другой, а может остаться той же. С помощью набора таких комбинаций можно попытаться собрать головоломку.

Онлайн Леннон

  • Ветеран
  • *****
  • Сообщений: 1 089
  • Пол: Мужской
  • Спящий.
Re: Программы для решения головоломок, Filler3d
« Ответ #7 : 10 Марта 2014, 14:20:19 »
Я заметил что в основе как правило коммутаторы, например R U'R' U. Но
сами комбинации могут быть очень сложными - например тридцать ходов в
определенной последовательности.

Можно решать бандажи даже не зная точно этих комбинаций. Просто сборка в
 этом случае получается не совсем стабильной - если угадал ход, то
решаешь бандаж минут за пятнадцать, не угадал - бандаж решается через
полтора часа.
В целом вероятность найти нужный ход довольно высокая - бандажи
величиной 3*3*3, отнимают обычно не дольше пары часов, если вариант
простой, то не более 5 минут.
« Последнее редактирование: 10 Марта 2014, 14:31:06 от Леннон »
F R U L D * 252

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #8 : 30 Марта 2014, 13:08:42 »
Не подскажите, где можно взять программу 3dSolver и где она обсуждается. Или перешлите мне ее на kosshams@mail.ru. Я хочу сравнить со своей программой.

Оффлайн grigr

  • Глобальный модератор
  • *****
  • Сообщений: 2 762
  • Пол: Мужской
  • кручу-верчу
    • Мой Магазин
Re: Программы для решения головоломок, Filler3d
« Ответ #9 : 30 Марта 2014, 14:27:35 »
я в первые слышу о ней

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #10 : 31 Марта 2014, 12:52:46 »
По первому разу посмотрел программу BurrTools: http://burrtools.sourceforge.net/, которая является улучшением программы  PuzzleSolver3D. По сравнению с моей программой она в трехмерном случае работает не только с кубической сеткой, но и 4 другими видами, обладает алгоритмом нахождения маневров для разборки решения (только для кубической решетки) и многими другими возможностями. В чем-то интерфейс менее удобен, чем в моей программе. Алгоритм, наверное, подобный моему. На маленькой задаче получилось похожее время. Наверное, какие-то возможности моей программы, не реализованы в BurrTools, но их не сложно доделать. Объем исходников BurrTools в 5 раз больше, чем у меня. Я не использую сторонних библиотек, только базовые компоненты VCL (в Builder'е), а они используют несколько, в том числе для трехмерного рисования.

В описании BurrTools говорится, что случай диагональной половинки куба моделируется 4 определенными кубиками из куба 2x2x2. Эта идея для меня является ценной, так как я задумывался, как реализовать этот случай. Теперь оказывается, что при желании можно его просчитать, ничего не добавляя в программе. 

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #11 : 19 Февраля 2015, 00:45:27 »
Существенно продвинул свою программу Filler3d: http://kosshams.ru/Files/Filler3d/Filler3d.exe.
Реализовал решение следующих задач и следующие возможности:
1) Симметриксы - составление симметричной фигуры.
2) Покрывашки -  нахождения формы, которую можно независимо заполнить фигурками из 2 наборов.
3) Получение возможных сдвигов фигурок или их групп. Может пригодиться в сложных 3-мерных задачах.
4) Решение задачи для выделенного подмножества фигурок, а не для всех нарисованных (флажек "Только выделенные").

Красными стрелками показаны кнопки, которые нужно нажать для вызова соответствующих окон.

Условия, накладываемые на варианты заполнения. Эти условия могут быть в любой комбинации. Пока не реализовано нахождение нужных конфигураций фигурок без размещения их в указанном пользователем полем. В этом случае для нахождения симметриксов и покрывашек нужен отдельный алгоритм. Для симметриксов на квадратной сетке я существенно улучшил программу FindSym: http://kosshams.ru/Programs/FindSym/FindSym.htm, но пока не выложил ее.

Получение возможных сдвигов фигурок:

Здесь 2 фигурки уже вынуто из куба. Это реализовано тем, что выделены все кроме них и отмечен флажек "Показ только выделенных".

3 симметричные фигуры, полученные из заданного набора фигурок.

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

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

Буду рад использованию и тестированию этой программы. Сообщайте о всех замеченных, пусть мелких, ошибках. (Кроме 2 неточностей в отрисовке 3-d, о которых я знаю.)
« Последнее редактирование: 03 Марта 2015, 05:27:36 от kosshams »

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #12 : 19 Февраля 2015, 21:38:13 »
Обновил программу по приведенной выше ссылке (http://kosshams.ru/Files/Filler3d/Filler3d.exe). Небольшое изменение, до которого я только сейчас додумался, сильно увеличило быстродействие в случае пустых клеток на поле. Также исправил одну ошибку.
« Последнее редактирование: 19 Февраля 2015, 21:40:15 от kosshams »

Оффлайн PhotoDreamer

  • Новичок
  • *
  • Сообщений: 23
  • Пол: Мужской
  • Профессия, образ жизни и диагноз - дизайнер.
    • Персональный сайт Андрея Устюжанина
Re: Программы для решения головоломок, Filler3d
« Ответ #13 : 20 Февраля 2015, 10:55:58 »
ЗдОрово! Радует то, что в вашей программе есть возможность решать задачи (плоские, по крайней мере) с фигурами произвольной формы, а также создавать симметричные задания. Вот как раз на этом форуме была опубликована такая задача: http://woodenpuzzle.smartbb.ru/viewtopic.php?f=43&t=62

Как говорится, сон в руку!

Большое спасибо за новость и ваш труд! Обязательно скачаю вашу программу и начну пользоваться. И ссылку на нее размещу на своем сайте (если это можно, конечно), разумеется, с указанием автора. 

А не планируете добавить в свою программу возможность решать головоломки со взаимным вращением или т.н. координатным перемещением элементов в процессе решения? Например, таких: http://puzzlewillbeplayed.com/Plank/Play3Cube/ (там в условии присутствуют слова "Rotation required.")

И еще: не задумывались ли Вы над добавлением в свою программу работы со цветом? Имею в виду, не только назначение всей детали какого-то цвета, а как бы разбиение ее на части или геометрическое "раскрашивание", и сопоставление в последствии этих разноцветных частей - например, складывание узоров из квадратиков, составление мозаик и т.п.

Вот пример, как я "запрограммировал" "BurrTools" на решение головоломки "4 цветных кубика": http://woodenpuzzle.smartbb.ru/viewtopic.php?f=39&t=28&start=10

Но это, Вы понимаете, уже "танцы с бубном". А вот чтобы сразу, на уровне стандартных возможностей программы...
« Последнее редактирование: 20 Февраля 2015, 11:58:54 от PhotoDreamer »
Раздел "Деревянные головоломки" на моем персональном сайте: http://www.photodreamstudio.ru/puzzle/puzzle-01.shtml

Оффлайн kosshams

  • Новичок
  • *
  • Сообщений: 18
  • Пол: Мужской
Re: Программы для решения головоломок, Filler3d
« Ответ #14 : 20 Февраля 2015, 19:58:14 »
В моей программе только один пространственный случай - кубическая решетка. Но с помощью не мной открытых приемов можно сэмулировать различные деления куба:
1) Диагональные половинки куба:

2) Пирамидки от центра куба к его граням (перекрестия пустые):



Но для пространственного случая работают все виды условий, например, симметричная фигура, антислайд, покрывашки.

В BurrTools можно раскрашивать кубики и грани. У меня пока этого нет. Есть только шахматная раскраска для квадратной, кубической и треугольной клетки.
А не планируете добавить в свою программу возможность решать головоломки со взаимным вращением или т.н. координатным перемещением элементов в процессе решения? Например, таких: http://puzzlewillbeplayed.com/Plank/Play3Cube/ (там в условии присутствуют слова "Rotation required.")
Для этой задачи как раз подошло бы раскрашивание кубиков и фигурок и поля в 2 цвета - по-своему, в отличие от шахматной раскраски. Но вообще, различных дополнительных условий можно придумать очень много, в том числе, связанных с раскраской. Некоторые головоломки с раскраской решаются фиксацией ориентации фигурок, что в моей программе можно сделать. Пока еще больше загромождать программу я не хочу. Должна быть какая-то красивая идея, чтобы имело смысл это делать. Ведь нельзя объять необъятное.
Что касается вращения, то это для сборки-разборки. Моя программа находит способ расположения, а также может помочь вынуть одну фигурку или их группу (без маневров). Вынуть вращением слишком сложно для программирования.
Вообще, после фигур по клеточкам следующим усложнением было бы многоугольные фигурки с произвольными длинами сторон и углами. Если там есть пустоты - это еще сложнее. Далее сдвигашки с поворотами. Программированию могли бы поддаться и топологические задачи с веревками, а также разнимание проволочных, веревочных и произвольных пространственных фигур. Но думаю, что этим нужно заниматься не совсем врукопашную. Что я под этим подразумеваю, если интересно, могу раскрыть. Также сложной задачей является решение сдвигашек с большим количеством фигур, когда нельзя перебрать все варианты. Тут нужна логика, какие-то критерии типа близости к решению не помогут.

Вот пример, как я "запрограммировал" "BurrTools" на решение головоломки "4 цветных кубика": http://woodenpuzzle.smartbb.ru/viewtopic.php?f=39&t=28&start=10
Для подобных простых с точки зрения алгоритма головоломок можно в два счета написать программу. Вопрос в том, как сделать доступным из пользовательского интерфейса решение таких задач. Есть какие-то мысли на этот счет. Но естественно, одному программисту за подобные задачи не стоит браться (тем более, одному за все задачи).

Как я уже написал в http://twistypuzzles.ru/forum/index.php/topic,684.0.html , я могу сделать программу по сдвигашкам, но боюсь, что ограничу аппетиты только некоторым подмножеством задач, которые я уже сам для себя обрисовал.