Comments 31
Похоже на проблему типа Dynamic Programming
Преобразуем в задачу SAT и не надо ждать 6 часов.
Интересно. Это вот это имеется в виду? Можете чуть детальнее рассказать как можно было решить задачу вашим методом?
Очень просто. Каждое возможное положение каждой фигуры обозначаете одной булевской переменной. Затем записываете уравнения конфликтов между пересекающимися фигурами. Потом, поскольку каждая фигура встречается один раз — конфликты между вариантами фигур одного типа и, наконец, по одному уравнению для каждой фигуры, которое говорит, что должен присутствовать хотя-бы один вариант. Сохраняете это в файл cnf, скачиваете какой-нибудь SAT солвер и получаете решение. Затем добавляете уравнение, исключающее данное решение, запускаете SAT солвер еще раз и получаете другое решение. И так до тех пор, пока решения существуют.
Пост заставил меня задуматься, что решение такой «простенькой» задачки, заняло бы у меня несколько месяцев :(
К сожалению это все возможные вращения того самого варианта, которое было найдено вручную. То есть у Галакуба есть только одно решение.Так человек в очередной раз качеством вычислений задавил компьютерное количество.
Но теперь есть метод, которым можно решить любую подобную задачу… Кстати, любопытно — можно играть на скорость с компьютером в сборку подобных головоломок.
так задачи были разные.
У человека изначально стояла одна задача — найти решение.
А у компьютера (если быть точным, у программиста) стояла другая задача — узнать, возможны ли другие решения.
При чём это не «найти ещё одно решение» — ведь человек может бесконечно думать и не находить другого решения, но это не будет значить, что его нет.
У человека изначально стояла одна задача — найти решение.
А у компьютера (если быть точным, у программиста) стояла другая задача — узнать, возможны ли другие решения.
При чём это не «найти ещё одно решение» — ведь человек может бесконечно думать и не находить другого решения, но это не будет значить, что его нет.
Почему-то мне кажется, что задача решает за секунды, видимо не все у вас оптимизировано. Хотя может это такой Питон.
Можете, пожалуйста, проверить существование решения в аналогичной головоломке?
Мне когда-то подарили заранее разобранную головоломку, идейно она проще: в куб 5×5×5 надо вставить 25 одинаковых фигур. Каждая фигура состоит из 5 кубиков вот такой конфигурации:
Самостоятельно не смог найти решения пока ни разу. Проверкой на чётность вроде должна иметь решение.
К сожалению я никогда не имел дела с питоном, а в коде в некоторых местах захардкожено что куб 4×4×4, не смог догадаться где всё заменить.
Код моей беспомощной попытки переделать repl.it/Bbfo/0
Мне когда-то подарили заранее разобранную головоломку, идейно она проще: в куб 5×5×5 надо вставить 25 одинаковых фигур. Каждая фигура состоит из 5 кубиков вот такой конфигурации:
##
###
Самостоятельно не смог найти решения пока ни разу. Проверкой на чётность вроде должна иметь решение.
К сожалению я никогда не имел дела с питоном, а в коде в некоторых местах захардкожено что куб 4×4×4, не смог догадаться где всё заменить.
Код моей беспомощной попытки переделать repl.it/Bbfo/0
Годно!
> Поставить на него какие-то библиотеки — это задача покруче, чем написать саму программу.
В чем трудности? brew, pip и вперед
В чем трудности? brew, pip и вперед
.
Любопытная задача.
Ваш вариант головоломки содержит только одну «загогулину». Интернет показывает наличие других вариантов, если я правильно понял, этой же задачи: https://i.ytimg.com/vi/QP4sMtPQj_Y/maxresdefault.jpg — здесь видно две загогулины. Даже если это не так, на мгновение представим, что у нас есть две или более загогулины.
Так вот. Эти загогулины не являются выпуклыми, так что хоть под неё и есть место, она может не вставиться из-за блокирующих элементов вокруг. Иначе говоря, важен порядок вставки элементов. Очевидно, что модель, реализующая сборку в таких условиях не должна ограничиваться перестановкой элементов, но и реализуемостью их вставки (то есть учитывать порядок вставки).
И теперь, собственно, главный вопрос к людям опытным в этой области: может ли оказаться решение допустимое теоретически, но неосуществимое физически из-за невыпуклости элементов?
Ваш вариант головоломки содержит только одну «загогулину». Интернет показывает наличие других вариантов, если я правильно понял, этой же задачи: https://i.ytimg.com/vi/QP4sMtPQj_Y/maxresdefault.jpg — здесь видно две загогулины. Даже если это не так, на мгновение представим, что у нас есть две или более загогулины.
Так вот. Эти загогулины не являются выпуклыми, так что хоть под неё и есть место, она может не вставиться из-за блокирующих элементов вокруг. Иначе говоря, важен порядок вставки элементов. Очевидно, что модель, реализующая сборку в таких условиях не должна ограничиваться перестановкой элементов, но и реализуемостью их вставки (то есть учитывать порядок вставки).
И теперь, собственно, главный вопрос к людям опытным в этой области: может ли оказаться решение допустимое теоретически, но неосуществимое физически из-за невыпуклости элементов?
С таким подходом однозначно надо попробовать Eternity II
Кстати, возможное количество положений загогулины 576 а не 288.
Sign up to leave a comment.
Решение головоломки Галакуб на Питоне