Решение головоломки Галакуб на Питоне

[Daniyar94]

Похоже на проблему типа Dynamic Programming

[A1ien]

Интуитивно — похоже, но вот как выделить функцию задачи которую уже можно было бы решать методом динамического прогаммированния — мне пока не очевидно.

[r4nd0m]

Если вы про целевую функцию, то можно взять незаполненный объём и минимизировать его до нуля. Или заполненный объём в пределах кубика, и максимизировать его до объёма кубика. Или минимизировать количество оставшихся фигур до нуля при условии невыхода за границу кубика.

[andy_p]

Преобразуем в задачу SAT и не надо ждать 6 часов.

[semenyakinVS]

Интересно. Это вот это имеется в виду? Можете чуть детальнее рассказать как можно было решить задачу вашим методом?

[andy_p]

Очень просто. Каждое возможное положение каждой фигуры обозначаете одной булевской переменной. Затем записываете уравнения конфликтов между пересекающимися фигурами. Потом, поскольку каждая фигура встречается один раз — конфликты между вариантами фигур одного типа и, наконец, по одному уравнению для каждой фигуры, которое говорит, что должен присутствовать хотя-бы один вариант. Сохраняете это в файл cnf, скачиваете какой-нибудь SAT солвер и получаете решение. Затем добавляете уравнение, исключающее данное решение, запускаете SAT солвер еще раз и получаете другое решение. И так до тех пор, пока решения существуют.

[semenyakinVS]

А не выйдет то же решение, что и у автора статьи, просто выполненное SAT-солвером?.. Вообще, если честно, пока с трудом пониманию о чём речь. Если будет время — напишите пример как могут выглядеть эти уравнения.

[andy_p]

Ну, например, уравнение (которое на самом деле называется клозом), того, что вариант 1 для одной фигуры не может быть одновременно с вариантом 2 для другой фигуры (то есть они пересекаются):

(not x1) or (not x2) = 1

[guyfawkes]

А что вы подразумеваете под «конфликтами»?

[andy_p]

Когда две фигуры пересекаются.

[Ambassadorik]

Пост заставил меня задуматься, что решение такой «простенькой» задачки, заняло бы у меня несколько месяцев :(

[KvanTTT]

На Питоне?

[Wesha]

К сожалению это все возможные вращения того самого варианта, которое было найдено вручную. То есть у Галакуба есть только одно решение.

Так человек в очередной раз качеством вычислений задавил компьютерное количество.

[semenyakinVS]

Но теперь есть метод, которым можно решить любую подобную задачу… Кстати, любопытно — можно играть на скорость с компьютером в сборку подобных головоломок.

[Ghool]

так задачи были разные.
У человека изначально стояла одна задача — найти решение.

А у компьютера (если быть точным, у программиста) стояла другая задача — узнать, возможны ли другие решения.
При чём это не «найти ещё одно решение» — ведь человек может бесконечно думать и не находить другого решения, но это не будет значить, что его нет.

[KvanTTT]

Почему-то мне кажется, что задача решает за секунды, видимо не все у вас оптимизировано. Хотя может это такой Питон.

[vovkasolovev]

Можете, пожалуйста, проверить существование решения в аналогичной головоломке?
Мне когда-то подарили заранее разобранную головоломку, идейно она проще: в куб 5×5×5 надо вставить 25 одинаковых фигур. Каждая фигура состоит из 5 кубиков вот такой конфигурации:

##
 ###

Самостоятельно не смог найти решения пока ни разу. Проверкой на чётность вроде должна иметь решение.
К сожалению я никогда не имел дела с питоном, а в коде в некоторых местах захардкожено что куб 4×4×4, не смог догадаться где всё заменить.

Код моей беспомощной попытки переделать repl.it/Bbfo/0

[CnapoB]

У самого такая есть, вот описание решения на JavaScript: JSFiddle, GitHub.

[vovkasolovev]

О, она решается! Отлично, спасибо!

[p53]

Не сочтите за рекламу, но вот пост, а вот само решение.

[andy_p]

Подозреваю, что SAT solver справится быстрее.

[p53]

Было бы интересно понять, за счёт чего.

[andy_p]

В рассмотренном выше методе используется одна эвристика — начинать перебор со столбцов с минимальным количеством вариантов, а SAT solver использует значительно большее количество эвристик.

[p53]

Если бы у вас получилось прогнать эту задачу на SAT солвере и показать прирост скорости, было бы здорово.

[andy_p]

Проверил на разных задачах такого плана. Результат — если решений мало, то выигрывает SAT, если много — то перебор.

[IDMan]

Годно!

[igrishaev]

> Поставить на него какие-то библиотеки — это задача покруче, чем написать саму программу.
В чем трудности? brew, pip и вперед

[Zagrebelion]

.

[doozza]

Любопытная задача.

Ваш вариант головоломки содержит только одну «загогулину». Интернет показывает наличие других вариантов, если я правильно понял, этой же задачи: https://i.ytimg.com/vi/QP4sMtPQj_Y/maxresdefault.jpg — здесь видно две загогулины. Даже если это не так, на мгновение представим, что у нас есть две или более загогулины.

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

И теперь, собственно, главный вопрос к людям опытным в этой области: может ли оказаться решение допустимое теоретически, но неосуществимое физически из-за невыпуклости элементов?

[rodem]

С таким подходом однозначно надо попробовать Eternity II

[andy_p]

Кстати, возможное количество положений загогулины 576 а не 288.