У вас есть два варианта. Оба имеют свои преимущества и недостатки, поэтому вы можете объединить идеи обоих в свое решение.
Вариант 1: написать эвристику
Подумайте о ситуациях, которые делают игру невозможной для решения (например, застревание в кольце блоков стен). Обнаружьте такие ситуации и напечатайте «больше не двигайтесь», как только такая ситуация возникнет. Чем больше таких ситуаций вы сможете придумать и реализовать, тем лучше будет ваш алгоритм.
Преимущество: легко и быстро.
Недостаток: в некоторых случаях игра неразрешима, но ваш алгоритм ее не обнаруживает.
Вариант 2: Написать решатель
Напишите программу, которая с учетом состояния вашей игры (где находится игрок, где находятся блоки и т. Д.) Выводит список шагов, которые можно предпринять для решения игры (или null или какое-то другое специальное значение, когда решения больше нет - это ваш случай "больше никаких ходов").
Как реализовать что-то подобное, зависит от точных правил игры. Простой подход состоит в том, чтобы выполнить Поиск в ширину в Игровом дереве : каждый узел в вашем дереве является игровым состоянием, а каждая дуга между узлами является возможным действием, которое игрок может выполнить может взять (двигаться вверх, двигаться вниз и т. д.).
Преимущество: надежно определяет, когда игру больше нельзя выиграть. Кроме того, эта программа может использоваться, чтобы давать подсказки игроку, когда он застревает.
Недостаток: в зависимости от сложности вашей игры вычисление решения может занять много лет. Для очень простых игр это может сработать; для некоторых простых игр это может занять очень много времени, а для довольно сложных игр, таких как шахматы или шашки, это очень сложно или невозможно.