Я знаю, что это старый вопрос, но я сталкивался с этим, когда решал проблему сам. Ни один из ответов здесь не является идеальным, и некоторые из них имеют сложные предостережения или нарушат патологические схемы. Вот мое решение:
Решите доску (вперед, а не назад) с неотмеченными плитками. Удалите две бесплатные плитки одновременно. Вставьте каждую пару, которую вы удаляете, в стек «подходящей пары». Часто это все, что вам нужно сделать.
Если вы зашли в тупик (numFreeTiles == 1), просто перезагрузите ваш генератор :) Я обнаружил, что обычно я не захожу в тупик, и до сих пор у меня было максимальное число повторов 3 для 10- или так раскладки я пробовал. Как только я нажму 8 попыток, я сдаюсь и просто случайным образом назначаю остальные плитки. Это позволяет мне использовать один и тот же генератор как для настройки доски, так и для функции перемешивания, даже если игрок облажался и перешел в 100% неразрешимое состояние.
Другое решение, когда вы попадаете в тупик, состоит в том, чтобы отступить (выскочить из стека, заменить плитки на доске), пока вы не выберете другой путь. Выберите другой путь, убедившись, что вы подбираете пары, которые удаляют исходную блокирующую плитку.
К сожалению, в зависимости от платы это может зацикливаться вечно. Если в итоге вы удалите пару, которая напоминает дорогу «без розетки», где все последующие «дороги» являются тупиковыми, и есть несколько тупиков, ваш алгоритм никогда не завершится. Я не знаю, возможно ли спроектировать плату там, где это будет иметь место, но если это так, решение все еще есть.
Чтобы решить эту большую проблему, обрабатывайте каждое возможное состояние платы как узел в группе обеспечения доступности баз данных, причем каждая выбранная пара является ребром на этом графике. Произведите случайный обход, пока не найдете листовой узел на глубине 72. Следите за своей историей обхода, чтобы вы никогда не повторяли спуск.
Поскольку тупики встречаются реже, чем решения первой попытки в макетах, которые я использовал, сразу приходит на ум гибридное решение. Сначала попытайтесь решить это с минимальным объемом памяти (сохраните выбранные пары в вашем стеке). После того, как вы попали в первый тупик, переходите к полной маркировке / генерации ребер при посещении каждого узла (ленивая оценка, где это возможно).
Я очень мало изучал теорию графов, поэтому, возможно, есть лучшее решение для задачи случайного обхода / поиска DAG:)
Редактировать: На самом деле вы могли использовать любое из моих решений с созданием платы в обратном порядке, а именно сообщение от 13 октября 2008 года. У вас остались те же предостережения, потому что вы все равно можете оказаться в тупике. Генерация доски в обратном порядке имеет более сложные правила. Например, вы гарантированно потерпите неудачу в настройке, если не начнете, по крайней мере, НЕКОТОРЫЕ из своих строк с первой части посередине, например, в макете с 1 длинной строкой. Выбор совершенно случайного (легального) первого хода в генераторе решения с большей вероятностью приведет к решаемой доске.