[алгоритмы][заведомо баян][почти пятница] Перечислить все валидные карты для сокобана

Может пойти от обратного ?

А подробнее?

http://en.wikipedia.org/wiki/Sokoban#Scientific_research_on_Sokoban

Как вариант, сгенерировать решенную задачу, а потом все ящики поперемещать, но только надо додумать алгоритм

Может пойти от обратного ?

А подробнее?

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

В общем жесть.

P.S. Надеюсь 20 шагов, это 20 перемещений ящиков, а не просто перемещений персонажа. А то ведь можно «сжигать» ненужные перемещения просто двигаясь туда-сюда.

Забыл сказать. Начальное множество вариантов расположения стен и ящиков это состояние уже решенной задачи. Надеюсь все поняли, что тут движемся «назад во времени».

Про генерацию уровней по твоей ссылке ничего не сказано.

> сгенерировать решенную задачу, а потом все ящики поперемещать

Львиная доля полученных таким способом задач будет иметь тривиальные решения (в 2-3-5 перемещений ящиков, а не в 20).

> Я так понимаю перебираем все множество вариантов расположения стен и ящиков. Для каждого множества определяем ......

Если «в лоб» перебирать все множество расположений стен (даже без учета ящиков), то с игровым полем 8х8 это 2^64 варианта. В разумный срок нам их не перебрать.

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

судя по рабочим картам сокобана, никто не перебирал все множество решений - скорей всего была реализована «решалка» конкретного поля, а дальше уже дизайнер рисовал красивое поле, и «игрался» с интересными вариантами, подбирая адекватное по сложности

Впервые прочитал про сокобан в каком-то журнале. Там были скрины 2 уровней.
Написал реализацию, для Spectrum, на basic. Символьная графика и всё такое - но было плавно (дробные символы) и прикольно. А вот карт придумать не смог - на том и забросил...
Ну а по сабжу - чует моё сердце -только лобовой перебор, если нужно покрыть ВСЕ возможные варианты, иначе задачка потянет на диссертацию по топологии.
Если надо просто много то можно придумать что-то типа алгоритма «отображения» одного уровня в идентичный, но с другим риснком.
Не забываем что будет ещё куча уровней, где «сжигать» ходы можно будет даже двигая ящик.