Алгоритм для решения задачи с колбочками

Всем привет. Набрёл на такую игру (таких игр не мало, это один из представителей) - https://play.google.com/store/... ort.Puzzle
Есть идеи какой алгоритм подойдёт для генерации проходимых или проверки решаемости случайно сгенерированных уровней?
Видел уровни с 13 колбами, 11 из которых были заполнены шарами 11 цветов.

Буду рад любым идеям. Есть ощущение, что уже давно придуманы/прописаны алгоритмы для решения подобных задач, просто я с ними раньше не работал.

0

ANTOH24, меня в гугле забанили, помочь не могу....
да и не культурно кидать ссылки, а не описать задачу своими словами

0

Согласен, поступил некрасиво, постараюсь исправить ситуацию.

Есть N колбочек, от 4 до 11 штук, заполненных шарами, а также 2 свободные. Шары разноцветные, по 4 шара одного цвета. В уровне с 6 заполненными колбами будет 6 цветов. В каждую колбу можно вместить только 4 шарика
Переставить шар можно только в пустую колбу или в колбу, в которой меньше 4 шаров и верхний шар того же цвета, что и переставляемый. Победа в уровне достигается сортировкой всех шаров по цветам в колбах. На скриншоте старт уровня.

Миниатюры

 

0

Сообщение от ANTOH24 Есть идеи какой алгоритм подойдёт для генерации проходимых или проверки решаемости случайно сгенерированных уровней?

Что-то мне подсказывает, что при таких ограничениях это разрешимо всегда. Принцип Дирихле, все дела, но за доказательством не ко мне.

0

Поиск по дереву состояний.

0

Приветствую вас, коллеги.
Тоже столкнулся с этой задачкой...
Давеча решил прикрутить на информационный терминал в коридоре ещё одну игру, чтобы дети игрались пока родители в очереди сидят. BUBBLE SORT (не путать с сортировкой массивов), или по-нашему - "Шарики в колбочках", "Шарики в пробирках".
В интернетах поговаривают, что некоторые особо упоротые игроки в эти "пузырьки" дошли уже до 5000+ уровня. Интеиция мне подсказывает, что не существует на планете такого китайца, который сидел бы и вручную создавал пятьтыщщ уровней для этой игры. А значит, они процедурно генерируются.
Создал (в VB6) рабочую модель игры, где шарики рандомно получают цвета. Вот только не все комбинации являются решаемыми.
Если в случае начального 2+1 (то есть: 2 пробирки с 8 шарами двух цветов + 1 пустая) всё вроде бы всегда сходится,
то в варианте 3+1 часть комбинаций - неразрешимые. Заметил, что если в средних рядах (втором и третьем) лежат шары одинакового цвета, то паззл не сложится. ...Но иногда блин складывается! Наверняка есть ещё одна зависимость, которую я визуально никак не прослежу.

С вариантами 4+1 ещё сложнее.
Хотелось бы узнать по какому алгоритму отбираются непроходимые варианты.
В некоторых вариантах игры видел, что в случае 3+ цветов просто используют две пустые пробирки.
НО ВОТ ЭТА же комбинация успешно разрешима!
Значит есть возможность проходить задачи с одной пустой пробиркой!

...В планах ограничиться только пятью цветами шаров (а то дети с родителями в коридоре ночевать будут))

Миниатюры

 

0

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

0

Да, нужна проверка решаемости.

У меня в программе 4 уровня сложности
1) 2 + 1 пустая
2) 3 + 1 пустая
3) 4 + 1 пустая
4) 5 + 1 пустая
Как показал на картинке выше, 4 цвета возможно решить с одной пустой пробиркой.
Возможно, и для 5 цветов это тоже возможно, главное знать по какому алгоритму отсеять нерабочие варианты.

...Если эта затея не выйдет, придётся не мучать голову и делать с двумя пустыми склянками...((

0

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

Вопрос, как управлять сложностью генерируемых уровней.

Добавлено через 16 минут
Как примерно генерировать самый сложный уровень обратным прохождением?

Исходное положение: n бутылок содержат упорядоченные шарики n цветов, m бутылок пустые.
Выбираем любой цвет и шарики этого цвета перекладываем на дно пустых бутылок по 1-2 шт. Выбираем следующий цвет и заваливаем полупустые бутылки этими шариками также по 1-2 шт. Можно третий цвет выбрать и также раскидать, но может и не надо усложнять дальше. Далее можно случайно перемешивать шарики. Но нет смысла трогать те шарики, которые уже были перемещены. Остановить генерацию в тот момент, когда уже все верхние шары передвинуты.

0

Сообщение от MrRoxMJ главное знать по какому алгоритму отсеять нерабочие варианты.

Ну а тупенько перебирать все ходы до тех пор пока не решится/заклинит? Вариантов здесь немного, нужно лишь предусмотреть зацикливание

0

Сообщение от Mikhaylo Генерировать можно обратным случайным прохождением

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

Сообщение от Mikhaylo m бутылок пустые

Если пустых колбочек более 1, то даже обсуждать нечего. С двумя пустыми пробирками паззл успешно складывается всегда. Но по сложности такой паззл примитив. Мне потому и захотелось заморочиться на вариант с одной пустой колбой, в котором игрок на несколько ходов вперёд думать должен.
Если добавлять в код программы на этапе генерации различных проверок типа "не завали проход".... То по сути мы в итоге приходим к коду автосборщика паззла - как предложил Igor3D

Сообщение от Igor3D перебирать все ходы до тех пор пока не решится/заклинит

.

Коллеги, говорят сейчас нейросети такие бошковитые, что за прогеров код пишут)) А что если скормить эту игру нейросети (не VB6 код, а саму игру с одной пустой пробиркой), чтобы она перебрала миллионы рандомно сгенерированных комбинаций и вывела ту самую искомую мной закономерность в расстановке шаров - при которых игра тупиковая, а при которых решаемая? )))

0

Сообщение от MrRoxMJ Рекурсия, увы не получится. В игре есть правило - переложить шарик можно только на такого же цвета.

Так правила обратного прохождения другие. Правило-то одно: перекладывать за один ход можно шарики только одного цвета за ход, лежащие сверху в бутылках.



Добавлено через 5 минут

Сообщение от MrRoxMJ Если пустых колбочек более 1, то даже обсуждать нечего. С двумя пустыми пробирками паззл успешно складывается всегда.

Вы, видимо, мало играли в игру. Все зависит от соотношения чисел m, n, k.
n - полных бутылок (=количество цветов),
m - пустых,
k - высота бутылок (=количество шаров одного цвета).

Если n = 10, k = 4, то при m = 2 вполне играбельно.

Добавлено через 3 минуты
И не надо решать задачи нейросетями там, где уже предложено два варианта железобетонно рабочие.

0