Эту китайскую головоломку с деталями 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, которым пользуются его зарубежные коллеги. На вопросы по задаче заполнения я, наверное, ответил.
