того чтобы найти верное решение, требуется перебрать очень много вариантов. Необходимое количество «правильных» ходов, ведущих к выигрышу, на некоторых уровнях может достигать тысячи. Однако опытные игроки, вооруженные эвристикой, могут быстро отсеять в мозгу заведомо тупиковые варианты, тем самым существенно сузив область поиска.
Некоторые (заметьте, только некоторые) уровни игры могут быть решены "автоматически", с помощью определенных итерационных поисковых алгоритмов. С этой целью, например, была создана программа Rolling Stone, которая умеет самостоятельно проходить некоторые уровни сокобана. Она была разработана в недрах GAMES Group Университета Альберты (одной из провинций Канады). Сложные же уровни сокобана все еще не поддаются «автоматическому» прохождению.
нельзя допускать, чтобы два ящика оказались друг рядом с другом у стены (вы никогда их не вытащите оттуда: тянуть ящики нельзя, толкать два ящика тоже);
нельзя задвигать ящик в угол;
нельзя сдвигать ящики в квадрат 2x2.
Кроме того, могут возникнуть такие ситуации, когда ящиками будет заблокирована определенная область лабиринта. И любая попытка разблокировать эту область, подвинув ящик, приведет к одной из описанных выше ситуаций.
Вообще, игра сокобан хороший экзамен на логическое мышление. Действует лучше и надежнее всяческих многочисленных тестов. Причем для этого вовсе необязательно владеть сложным арсеналом приемов и стратегий. Достаточно освоить только несколько несложных правил. Моя жена (увидевшая эту игру впервые в жизни) прошла за пять минут сложнейший уровень, над которым я, играющий в сокобан не первый год, бился гораздо дольше. Вот вам и женская логика!
Как мы уже говорили, универсального алгоритма решения этой головоломки фактически не существует. Однако есть программы, которые позволяют упростить решение: вычислить предположительно правильные ходы на определенную глубину, помочь в записи решения на диск. Если забыть про математический формализм, существует ряд программ, которые с полным правом могут носить название "solver". Они действительно умеют решать многие, даже не самые простые уровни. Но и у них есть предел. Список таких программ можно найти на странице www geocities com/erimsever/sokoban5.htm. Там же приведены очень интересные диаграммы, показывающие количество вариантов ходов на разных этапах решения.
В мире шахмат существуют определенные правила записей ходов и позиций на доске. В мире сокобана тоже выработаны такие правила. План уровня и первоначальное положение объектов записывается в обычном текстовом файле с помощью следующих символов: "#" стены, "." пустое место, куда надо поставить ящик (так называемая "цель"), "@" человечек, "+" человечек, который стоит на той клеточке, где находится одна из целей, "$" ящик на пустом месте, "*" ящик на одной из целей. Такой формат записи получил название "XSB File Format". Файлы этого формата могут иметь расширения: xsb, sok, rdf, lp0, dat, pak и даже просто txt. Этот формат хранения уровней вы найдете во многих клонах сокобана.
Кстати, генерация уровней тоже не самая простая задача. Попробуйте создать новый уровень сокобана с нуля. Недостаточно просто нарисовать причудливый лабиринт и раскидать по нему ящики. Нужно чтобы уровень имел как минимум одно решение. Кстати, количество возможных вариантов решения определяет сложность
уровня.
Задача генерации уровней для сокобана так и просилась под клавиатуру программистов. Поэтому за годы существования игры появилось немало программ, которые умеют автоматически создавать интересные уровни, основываясь на различных исходных настройках. В качестве исходных настроек выступают, например, размер уровня по горизонтали и вертикали, количество ящиков, количество «пустого» пространства внутри лабиринта.
Есть еще более простой формат, где план уровня записывается в строчку. Такой формат удобен, например, для пересылки уровня по SMS (напомню, что имеется целый ряд мобильных версий сокобана). Уровень в таком формате выглядит, например, так:
[2-5#|3#3-#|#2-*#-2#|#-#2-*-#|#-*2-#-#|2#-#+2-#|-#3-$2#|-3#2-#|3-4#]
Цифрами обозначается количество повторений символа, который идет за этой цифрой. Символом "|" дается команда на начало новой строки.
Есть также отдельный формат для записей перемещений человечка по лабиринту. В нем все перемещения записываются буквами r, l, u и d (соответствующие четырем направлениям перемещений). Если при перемещении двигается ящик, то буквы записываются в верхнем регистре.
За годы своего существования сокобан превратился из простой логической игрушки в культовый объект. С каждым годом появляются все новые и новые версии этой игры. По нему пишут диссертации и научные статьи. Он оброс различными вспомогательными программами и файловыми форматами. Ну и кроме всего прочего, сокобан это неплохой способ убить время и потренировать мозги.
Софтерринки
Автор: Илья ШпаньковАдрес www codeode com/privacymantra/index html
Версия 2.03
Размер 463 Кбайт
Интерфейс английский (русский не поддерживается)
Цена бесплатно