Ну смотрите, гипотеза про разрешимость каждого хода и правда гипотеза. Я алгоритмов не видел Но тогда у нас есть два стула. Либо каждый ход в хорошем сценарии разрешим и это пазл. Либо игра может произвольно кинуть тебя в безвыходную ситуацию, потому рандом спаунов и ходов просто так списать с тебя ресурсы, что является сомнительным дизайном. На какой сядем?
Начнем с того, что во многих головоломок может быть несколько вариантов решения на текущем и последующих ходах, и их эффективность может быть вполне сопоставима. Т.е. совершенно не обязательно, что будет только один такой путь.
На счёт "игра может тебя произвольно кинуть в безвыходную ситуацию" - это, скорее, про плохой дизайн. Защита от такой ситуации, как правило, тщательно продумывается и тестируется.