Чтобы избежать поиска каждой достижимой позиции, вам понадобится способ быстро определить, является ли позиция неразрешимой. Вы не сможете быстро исключить все неразрешимые позиции, но вы можете исключить многие из них.
Одна вещь, которую нужно проверить, - это для каждого штампа D и для каждого отверстия H, возможно ли, чтобы штамп D достиг отверстия H. Даже это не так просто точно выяснить. В качестве консервативной границы вы можете сложить числа, оставленные на всех кубиках, предположить, что у D осталось так много движения (потому что каждое из этих движений теоретически может подтолкнуть D), и посмотреть, может ли D достичь H. Как чуть менее консервативный связывая, вы могли бы вместо этого назначить все лишние движения тому, кто умрет E ближе всего к возможности нажать D, а затем посмотреть, может ли D (с помощью E) достичь H.
После того, как вы определили, какие кости все еще могут достигать, в какие отверстия, если есть кубик, который не может достичь ни одного отверстия, или отверстие, которое не может быть достигнуто любым кубиком, положение становится неразрешимым , Точно так же, если есть N костей, которые не могут достичь N различных костей, или H отверстий, которые не могут быть достигнуты с помощью N различных костей, то положение неразрешимо.
Эта эвристика не полностью решит вашу проблему, но может сделать пространство поиска более управляемым для определенных диапазонов плат.