|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serg Belyaev 2:5015/166.7 08 Aug 2001 21:41:41
To : Vadim Guchenko
Subject : Sokoban (логическая игра)
--------------------------------------------------------------------------------
06-Aug-01 20:47:10, Vadim Guchenko wrote to All
Subject: Sokoban (логическая игра)
VG> Hi, All.
VG> Существует ли алгоритм прохождения лабиринтов игры Sokoban? Если
VG> кто не знает, там грузчик толкает ящики. Их нужно поставить на
VG> определенные места. Кто-нибудь занимался написанием солвера?
В понедельник скачал неплохой солвер:
www.xylo.freeserve.co.uk/nSk3v112.exe
(Takaken.Solver)
Сам также занимаюсь этой игрушкой. Для начала реализовал полный
перебор для небольших комнат - хотелось оценить число
возможных позиций. Побочным результатом была генерация
новых комнат - очень любопытных, например:
########
# # ##
# $. ##
# * * ##
#@#$# ##
# *.. ##
###$ #
### #
########
Вручную с подобными задачками справиться затруднительно,
а вот вышеприведенный солвер решает ее почти мгновенно.
Теперь об алгоритме.
Для некоторого сокращения рассматриваемых позиций я
пошел от конечной позиции, которой присвоил 0-ой уровень.
Если имеется набор i-ого уровня, то легко получить
набор i+1-го уровня, при этом ранее встреченные позиции
уже не включаются.
Да, забыл сказать, под позицией понимается упорядоченный
набор ящиков и связная область с человечком, которая
задается клеткой с минимальным номером (например).
В противном случае число позиций катастрофически вырастает.
Т.е. каждая реальная позиция сначала "нормализуется":
связная область определяется каким-либо алгоритмом
закрашивания, ящики сортируются.
В общем получается, что к i-ому уровню относятся те и
только те позиции, из которых можно достигнуть конечной
позиции за i перемещений ящиков (минимально).
Число позиций для приведенного выше примера по уровням
распределяется так:
1:5 6:55 11:153 16:119 21:139 26:443 31:351 36:87 41:15
2:9 7:74 12:149 17:99 22:189 27:468 32:290 37:55 42:11
3:19 8:96 13:134 18:83 23:254 28:450 33:215 38:39 43:6
4:27 9:124 14:136 19:84 24:321 29:415 34:168 39:30 44:2
5:39 10:148 15:127 20:105 25:397 30:376 35:125 40:21
Для более просторных комнат можно наблюдать сотни тысяч позиций,
выше мой алгоритм уже не может осилить.
Hо... большое число позиций обычно говорит о достаточно большой
свободе выбора и о простых решениях - наверняка в этом случае
должны хорошо работать простые эвристики (но я пока не пробовал).
<SVB>
--- Terminate 5.00/Pro
* Origin: Crazy Pentium III. (2:5015/166.7)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
