Можно ли проверить, разрешима ли головоломка с другим состоянием цели?

Question

Итак, у меня есть случайная 15-головоломка или любая N-головоломка с четной шириной, и у меня также есть случайное состояние цели.То есть пустая плитка и другие плитки также размещаются случайным образом.

Я могу проверить, разрешима ли головоломка 15 со стандартным состоянием цели, состоящим в том, чтобы плитки были в порядке и были пустыми в правом нижнем углу, норандомизация состояния цели кажется более сложной, чем стандартная головоломка 8.

Пример:

Start State
8    4    1   6
11   2    3   10
15   12   0   9
14   5    7   13

Goal State:
11   4    1   0
8    2    3   10
5    15   6   9
12   9    7   13

Правила стандартной решаемости из 15 головоломок:

Если ширина нечетная , то каждое разрешимое состояние имеет четное число инверсий.

Если ширина равна четное , то каждое разрешимое состояние имеет

• четное число инверсий, если пробел находится в нечетном ряду, считая снизу;

• нечетное число инверсий, если бланкна четном ряду, считая снизу;

Answer 1

Я не думаю, что разные цели влияют на разрешимость.

Самое простое решение, которое я могу придумать, - сопоставить числа в пользовательском состоянии цели с числами в стандартном состоянии цели.Например: для первой строки вы обрабатываете 11, как если бы это было 0, 4 -> 1, 1 -> 2, 0 -> 3 и т. Д.