Как построить разрешимый уровень в Same Game

Question

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

Мне нужно сделать функцию, чтобы решить эту проблему, чтобы в нее мог играть идеальный игрок навсегда.

У меня максимум 6 цветов и минимум 2, и доска имеет разумный размер (14x12), но может быть изменена.

Язык не имеет значения.

РЕДАКТИРОВАТЬ: мне не нужно решать головоломку, мне нужно создавать уровни, которые имеют хотя бы одно решение.

Answer 1

Я только что ознакомился с пятью различными версиями игры в Ubuntu, и я нашел ответ, от которого можно разграбить!

Портативная головоломка Саймона Тэтхэма

Я играю около пяти его игр непрерывно, но предпочитаю Same GNOME. Я только что загрузил его Same Game, и у него есть возможность гарантировать растворимость при создании пользовательских игр. Даже имеет настраиваемую систему начисления очков. Это все ужасно продвинуто.

Exe и исходный код доступны по ссылке выше.

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

Answer 2

Один метод, который, я добавлю, редко бывает самым эффективным, - это построить уровень в обратном порядке.

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

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

Вы можете взглянуть на исходный код для версии с открытым исходным кодом, такой как Тот же GNOME и посмотреть, как они это делают (если они вообще это делают!)

Answer 3

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

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

Answer 4

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

Answer 5

Я думаю, что лучше всего, если вы генерируете уровень случайным образом, я имею в виду добавление 1 или более блоков в одно и то же время к одному столбцу, так что у вас будет несколько соединительных блоков. Затем вы пишете простой алгоритм решения, который просто решает доску, пока больше нет возможных ходов. Затем вы просто пытаетесь завершить оставшуюся часть, просто нажимая несколько блоков сверху, чтобы у вас было еще несколько блоков, чтобы исчезнуть. Вы продолжаете, пока не закончите доску. Вы храните части, которые вы добавили в другой матрице. После этого вам просто нужно добавить 2-ю матрицу к 1-й сверху. Если доска не заполнена, вы просто должны заполнить доску блоками для начала (соединяющие блоки).