игра Катамино (Katamino)

[sergey83]

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

[Nilenbert]

Потому что гуглить надо по слову "пентамино" или "полиомино". Про них даже книжка есть : Голомб С.В. Полимино = Polyominoes / Пер. с англ. В. Фирсова. Предисл. и ред. И. Яглома. — М.: Мир, 1975. — 207 с., правда там математика, а не программирование.

[sergey83]

Спасибо!
Судя по книжке http://mathemlib.ru/books/item/f00/s00/ ... t015.shtml , чтобы определить, возможно ли замостить прямоугольник выданными полиомино, нужно использовать перебор, поиск с возвратом, как в задаче о 8 ферзях.
Но это результат сорока летней давности.
Знаете головоломку "игра в 15"?

Там поле четыре на четыре клетки, внутри двигаются 15 костяшек. Нужно расставить костяшки по порядку. Хорошо известно, что если поменять местами 14-ю и 15-ю костяшки местами, то путем перестановок головоломку невозможно собрать. Так вот, не обязательно производить перебор всех возможных перестановок, чтобы понять, что головоломка не соберется. Достаточно перед началом игры подсчитать какую-то формулу.
А еще для задачи о расстановке ферзей появились алгоритмы Магу, благодаря которым можно получить хотя бы одну расстановку ферзей. В соседней теме написали, что хоть миллион ферзей можно расставить за секунду topic32139.html
Т.е. раньше задача была головоломкой. А потом появились математические методы решения этой задачи без перебора. Больше не нужно придумывать эвристики, как ускорить поиск с возвратом.

Так, может, и по полиомино придумали какие-то алгоритмы?

[sergey83]

Меня заинтересовал методологический подход в решении головоломок. По-идее, если доказана NP-полнота задачи, то не стоит искать решение за самое короткое число ходов. Но тут я узнаю подробности про игру пятнашки http://ru.wikipedia.org/wiki/%D0%9F%D1% ... 0%BA%D0%B8 Доказано, что в игре пятнашки, а также обобщенные пятнашки (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения является NP-полной. Известно, что в игре пятнашки достаточно 80 ходов для сбора головоломки. Известно, что для сбора головоломки из такой конфигурации (1)

необходимо 80 ходов. И быстрее нельзя.
B тут я нахожу программу, которая но моем домашнем компьютере находит решение (1) из 80 менее, чем за 6 минут.
Я ничего не понимаю. Игра пятнашки является NP-полной. Я подсунул программе самый плохой случай. Почему программа так быстро нашла решение? Я ожидал, что NP-полную задачу нельзя решить быстрее, чем за $2^n$ шагов.
Т.е. в моем случае сложность нахождения решения конфигурации (1) должна была бы быть $2^{80}$ шагов. Даже чтобы добраться до глубины 80, необходимо было бы для начала перебрать все решения за 79 шагов. Т.е. перебрать $2^{79}$ шагов, убедится, что при такой глубине игру пятнашки не собрать, а потом искать решение за 80 шагов.

Еще раз приведу формулировку по обобщенным пятнашкам. Пусть имеется квадрат со стороной $n \cdot n$ и в нем $n \cdot n -1 $ костяшек. Вопрос, можно ли собрать головоломку за $k$ шагов. Так вот, такая задача является NP-полной.

Я ожидал, что сложность работы любого, даже эвристического алгоритма будет не быстрее $2^k$ шагов. А вот тут появляется программа, которая находит оптимальное решение за считанные минуты. Что-то у меня в голове не клеится!

[Urnwestek]

Значит, на других примерах она работает дольше или/и не всегда выдаёт оптимальный ответ. Там же не полный перебор, скорее всего, а какие-нибудь аб-отсечения/нейронки/отжиг/ещё-что-то-такое.

[sergey83]

А вот еще одна программа для решения головоломки пятнашка http://web.archive.org/web/201310172341 ... olver.html
И эта программа, и та, что я приводил выше, решают головоломку пятнашки за минимальное число шагов, причем за считанные минуты. У этих двух программ стояла цель, чтобы решить головоломку за минимально возможное число шагов.
Алгоритмом A* еще может решить укороченную головоломку пятнашка, где поле три на три клетки и 8 костяшек. Однако классическая игра пятнашка из 15 костяшек будет не по зубам алгоритму A*.
В википедии http://ru.wikipedia.org/wiki/%D0%90%D0% ... A%D0%B0_A* про алгоритм A* написано, что при удачно выбранной эвристике он может стать полиномиальным. Однако поиск крайтчайшего пути сборки головоломки пятнашка является NP-полной задачей.
Я не понимаю, как алгоритмы в приведенных выше программах могут обмануть NP-полноту и находить оптимальное решение головоломки пятнашка быстрее, чем за $2^{80}$ шагов.

[Xaositect]

sergey83 в сообщении #789840 писал(а):

Я не понимаю, как алгоритмы в приведенных выше программах могут обмануть NP-полноту и находить оптимальное решение головоломки пятнашка быстрее, чем за $2^{80}$ шагов.

Ну, если задача NP-полная, то отсечением полиномиальное решение не получится. А вот сделать из $2^n$ что-нибудь типа $2^{\alpha n}$ при помощи хорошего отсечения можно. NP-полнота не значит, что нужно перебирать все варианты, только значительную их часть.

[sergey83]

В игре Космические Рейнджеры есть такой квест, похожий на игру пятнашка

Там также поле четыре на четыре клетки, внутри двигаются 15 костяшек. Однако костяшки пронумерованы от 1 до 8. Некоторые костяшки встречаются дважды. Самое трудное в головоломке то, что есть ограничение на количество перемещений.
Если обычную головоломку пятнашка собирать вручную, слой за слоем, то на сборку уйдет примерно 200 перемещений. А в головоломке про Рейнджеров есть ограничение на количество перемещений. Простым алгоритмом головоломку не решить.
Вот тут можно скачать игру из Рейнджеров и самостоятельно с ней поиграться, попытаться собрать вручную http://www.mediafire.com/download/3bmm0 ... b/game.zip Игру Codebox.qm нужно открыть с помощью плеера.

-- Вт ноя 26, 2013 18:07:45 --

Вот я вздумал решить головоломку из Рейнжеров с помощью программы, находящей оптимальное решение головоломки пятнашка PuzzleSolver.jar from http://www.brian-borowski.com/Software/Puzzle/
Я перенумеровал 15 цифрами костяшки из головоломки про Ренджеров, загнал в решатель PuzzleSolver.jar А он мне заявляет, что это недопустимаю конфигурация головоломки пятнашка. Пришлось жульничать. Цифра 2 встречается два раза. Раньше при перенумерации я сначала костяшку 2 заменял цифрой 8, а потом второй раз костяшку 2 заменял цифрой 9. Теперь я решил пересставить местами костяшки 8 и 9 и загнать в решатель PuzzleSolver.jar. Такая конфигурация была принята решателем. Он выдал решение за сотые доли секунды. Мне осталось перевести, проинтерпретировать это решение, чтобы получить инструкцию для человека, как переставлять костяшки в скрипте про Рейнджеров:

1. фрагмент 5 выше пустой клетки
2. фрагмент 7 левее пустой клетки
3. фрагмент 1 левее пустой клетки
4. фрагмент 8 выше пустой клетки
5. фрагмент 5 левее пустой клетки
6. фрагмент 7 выше пустой клетки
7. фрагмент 6 правее пустой клетки
8. фрагмент 5 ниже пустой клетки
9. фрагмент 2 правее пустой клетки
10. фрагмент 4 правее пустой клетки
11. фрагмент 2 выше пустой клетки
12. фрагмент 3 левее пустой клетки
13. фрагмент 4 ниже пустой клетки
14. фрагмент 2 правее пустой клетки
15. фрагмент 7 ниже пустой клетки
16. фрагмент 1 левее пустой клетки
17. фрагмент 2 выше пустой клетки
18. фрагмент 2 левее пустой клетки
19. фрагмент 8 ниже пустой клетки
20. фрагмент 2 правее пустой клетки
21. фрагмент 1 правее пустой клетки
22. фрагмент 7 выше пустой клетки
23. фрагмент 2 левее пустой клетки
24. фрагмент 1 ниже пустой клетки
25. фрагмент 1 ниже пустой клетки
26. фрагмент 8 левее пустой клетки
27. фрагмент 4 левее пустой клетки
28. фрагмент 3 выше пустой клетки
29. фрагмент 2 правее пустой клетки
30. фрагмент 1 правее пустой клетки
31. фрагмент 8 ниже пустой клетки
32. фрагмент 5 правее пустой клетки

Изначально компьютер давал ограничение в 59 перемещений. А тут удалось решить головоломку за 32 перемещения. Я игрался, решал Рейнджеров с другими комбинациями костяшек. Самое длинное решение было из 42 перемещений. Причем программа PuzzleSolver.jar находила решение за сотые доли секунды.

А вот дальше интереснее. Некий GlukKazan написал программу для решения головоломки из Рейнджеров http://habrahabr.ru/post/180043/ Он использовал поиск с возвратом, отсечение по манхеттенскому расстоянию. Программа работает долго. Для поиска решений головоломки из Рейджеров, состоящее из 20 перемещений костяшек, тратится две с половиной секунды. А если решение состоит из 42 перемещений, то на его поиск требуется более 10 минут. PuzzleSolver.jar для игры пятнашка при подобных глубинах поиска тратит сотые доли секунды.
Но вот что интересно. Я свел головоломку из Рейнжеров к игре пятнашка и думал, что это решение оптимально. Конкретную позицию, размещенную на картинке, пятнашка решает за 32 хода. Однако программа GlukKazan решает именно головоломку из Рейнджеров. Так программа нашла решение головоломки не за 32, а за 20 ходов!

[sergey83]

Вот автореферат одной диссертации по пятнашкам

[sergey83]

Кубик Рубика удается перевести на язык теории групп. Вот для примера программа GAP собирает кубик Рубика за 100 ходов http://www.gap-system.org/Doc/Examples/rubik.html
Интересно, а GAP может ли собрать игру пятнашка? Я теорию групп не проходил.
Я думал, что игру катамино можно решить с помощью динамического программирования. Но не получилось.