Как проверить, что n-головоломка с двумя пробелами разрешима?

Question

Я изменил вопрос о n-puzzle. В этом сценарии головоломка состоит из двух заготовок вместо одной.

Initial State
3   5   1   
4   6   -   
7   2   -   


Goal State
-   1   7   
3   2   -   
5   6   4   

Есть ли какой-нибудь алгоритм, который я могу использовать для этого?

Answer 1

Все существующие алгоритмы, которые решают обычную головоломку с скользящей плиткой (например, A* или IDA*), также могут решить этот вариант. Головоломка с несколькими пробелами эквивалентна базе данных шаблонов для головоломки с раздвижной плиткой - точное решение головоломки с заменой некоторых частей на пробелы может использоваться в качестве эвристики для исходной головоломки только с одним пробелом.

(Чтобы быть точным, они эквивалентны базам данных аддитивных шаблонов. Вы можете объединить несколько вместе и сложить их эвристические значения, если стоимость действия замены двух пробелов равна 0 и ни одна из плиток не дублируется.)