Найдите любую последовательность ходов, которая может генерировать состояние платы Connect-4 при условии

Question

Учитывая действительное Connect-4 состояние платы в матрице A (6x7), где

A[i][j] = '0',  if empty,
A[i][j] = 'r',  if filled with red stone,
A[i][j] = 'y',  if filled with yellow stone.

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

Можно предположить, что красный всегда начинает игру.

Пример:

A = [0 0 0 0 0 0 0
     0 0 0 0 0 0 0
     0 0 0 y 0 0 0
     0 0 0 r 0 0 0
     0 0 0 y 0 0 0
     0 0 r r 0 0 0]

Valid sequence of moves:- 44443 

44443 означает ->
Первый игрок перемещается по столбцу № 4,
, затем Второй игрок перемещается по столбцу № 4, ... (принимая номера столбцов как 1-индексированные)

Мой подход : -
-) Сначала узнаем цвет последнего камня по соотношению количества непустых позиций. Пусть этот цвет будет last_coloured.
-) Затем возьмите с доски один самый верхний камень цвета last_coloured, рекурсивно продолжайте идти вперед, если не можете найти камень любого цвета last_coloured, затем возвращайтесь.

Хотя этот подход можно решить для доски 7 * 6 менее чем за 16 ^ 21 шагов.
(Редактировать: Спасибо @Prune за исправление этой верхней границы)

Вопрос 1) Есть ли более точная оценка числа шагов вышеупомянутого подхода?
Вопрос 2) Есть ли лучший подход?

Answer 1

Думайте об этом не как о Connect-4, а как о пасьянсе на одной доске. Ваша цель - убрать все камни. У вас есть правила удаления камней;теперь, это улучшило бы дерево поиска, если бы у вас была хорошая функция для оценки любой позиции доски.

Поскольку вы чередуете удаление цветов, у вас есть правило

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

Это также приведет к второстепенному члену в вашей функции eval: если ваш запас камня не сбалансирован, определите столбец (столбцы), где вам нужно получить награду за копку, чтобы получитьк скудному цвету.

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

Этого достаточно, чтобы заставить вас двигаться?