Маджонг - мозаики Расположения для обеспечения по крайней мере одного пути к победе, независимо от расположения

Играйте в игру наоборот.

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

Единственная вещь, которую я смог придумать, состоит в том, чтобы поместить мозаики вниз в соответствие парам как своего рода обратная игра Пасьянса Маджонга. Так, в любой точке во время размещения мозаики плата должна быть похожей, это посреди реальной игры (т.е. никакие мозаики, пускающие в ход 3 слоя выше других мозаик).

Если мозаики являются местом в соответствии парам в обратной игре, это должно всегда приводить по крайней мере к одному вперед путь для решения игры.

Я хотел бы услышать другие идеи.

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

Если Вы предпочесть подход "Большого взрыва" (генерирующий полный набор случайным образом вначале), являетесь очень мужественным разработчиком или просто чувствуете себя мазохистскими сегодня, Вы могли представить всех пар, которых можно взять из данного набора и как они зависят друг от друга через ориентированного графа.

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

Реализацию этого решения оставляют как осуществление читателю :D

Вот правила, которые я использовал в своей реализации.

Когда buildingheap, для каждого раздражения в паре отдельно, находят ячейки (места), которые являются:

• имеет все ячейки на более низких уровнях, уже заполненных
• место для второго раздражения не блокируется сначала, рассматривая, разъедают ли сначала уже помещенный на борту
• оба места "в краях" уже созданной "кучи":
  • У ЛЮБОГО есть по крайней мере один сосед в левой или правой стороне
  • ИЛИ это - первое раздражение подряд (все ячейки в правом и левом рекурсивно свободны),

Эти правила не гарантируют, что сборка всегда будет успешный - она иногда оставляет последние 2 бесплатного самоблокирования ячеек, и сборка должна быть повторена (или по крайней мере последние несколько раздражений) На практике, "черепаха", созданная в более никаких затем 6 повторениях.

Большинство существовавших игр, кажется, ограничивает помещение сначала ("сначала на строке") раздражения где-нибудь в середине. Это придумывает более удобные конфигурации, когда нет никаких раздражений в краях очень длинных строк, остающихся вплоть до последних игровых движений. Однако "середина" отличается для различных конфигураций.

Удача :)

P.S. Если Вы нашли алгоритм, которые создают разрешимую "кучу" в одном повороте - сообщенный мне.

Пасьянс? Просто предположение, но я предположил бы, что Ваш компьютер должен будет разбить игру (или близко к нему) для определения этого.

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

До некоторой степени Вы могли попытаться удостовериться, что одна из этих 4 мозаик является не больше, чем X слоями ниже еще X.

Большинство игр, которые я вижу, имеет команду перестановки для того, когда кто-то застревает.

Я попробовал бы соединение вещей и видел бы что работы лучше всего.

Я знаю, что это старый вопрос, но я столкнулся с ним, когда решал проблему сам. Ни один из ответов здесь не является идеальным, и некоторые из них содержат сложные оговорки или нарушают патологические схемы. Вот мое решение:

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

Если вы попадете в тупик (numFreeTiles == 1), просто перезагрузите генератор :) Я обнаружил, что обычно не попадаю в тупики, и пока что максимальное количество попыток равно 3 для 10 или около того макетов, которые я пробовал. После 8 попыток я сдаюсь и просто случайным образом распределяю остальные плитки. Это позволяет мне использовать один и тот же генератор как для настройки платы, так и для функции перемешивания, даже если игрок облажался и сделал 100% неразрешимое состояние.

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

К сожалению, в зависимости от доски, это может зацикливаться бесконечно. Если вы в конечном итоге удалите пару, которая напоминает дорогу «без выхода», где все последующие «дороги» являются тупиком и есть несколько тупиков, ваш алгоритм никогда не завершится. Я не знаю, можно ли спроектировать плату, где бы это было так, но если да, то решение все еще есть.

Чтобы решить эту большую проблему, рассматривайте каждое возможное состояние платы как узел в DAG. , где каждая выбранная пара является ребром на этом графе. Сделайте случайный обход, пока вы не найдете листовой узел на глубине 72. Следите за своей историей обходов, чтобы никогда не повторить спуск.

Поскольку тупики встречаются реже, чем решения первой попытки в схемах, которые я использовал, то, что сразу приходит на ум это гибридное решение. Сначала попробуйте решить его с минимальным объемом памяти (сохраните выбранные пары в стеке). Как только вы зайдете в первый тупик, переходите к полной маркировке / генерации ребер при посещении каждого узла (ленивое вычисление, где это возможно).

Я очень мало изучал теорию графов, так что, возможно, есть лучший вариант. решение проблемы случайного обхода / поиска в DAG:)

Редактировать: вы действительно можете использовать любое из моих решений с генерацией платы в обратном порядке, как сообщение от 13 октября 2008 года. У вас все еще есть те же предостережения, потому что вы все еще можете попасть в тупик. Однако создание доски в обратном порядке имеет более сложные правила. Например, вы гарантированно провалите настройку, если не начнете хотя бы НЕКОТОРЫЕ строки с первой частью посередине, например, в макете с одной длинной строкой. Выбор полностью случайного (допустимого) первого хода в генераторе прямого решения с большей вероятностью приведет к решаемой доске.

У вас есть 144 плитки в игре, каждая из 144 плиток имеет список блочных .. (Топ-плитка на стеке имеет пустой список блоков)

Все действительные движения требуют пустого пустой «ust Current__Vertical_Block_list». Это может быть матрица 144x144, так что 20K памяти плюс левый и правый блок, также 20 к каждому.

Создайте действительную таблицу перемещения из (Remaning_Tiles) и ((пустой текущий список вертикальных блоков) и ((пустой текущий список левых блоков) или (пустой текущий список правых блоков)))

Выбрать 2 случайных плитки от действительного Переместить таблицу, записывать их Обновите (текущие таблицы Vert, влево и вправо), запишите плитки, удаленные в стек

Теперь у нас есть список перемещений, которые представляют собой действительную игру. Назначьте соответствующие типы плитки к каждому из 72 ходов.

Для сложных игр отследится, когда каждая плитка становится доступной. Найти наборы, которые имеют (рано рано рано поздно) и (поздно поздно раньше), поскольку он пуст, вы найдете 1 EE 1 LL и 2 Le Blocks. Из 2 Le Block найдите раннее, что блокирует любой другой ранний, что ( кроме правой колодки левой стороны)
Как только у вас есть действительная игра, играй с заказом.