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

Итак, у меня есть случайная головоломка из 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 таковы:

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

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

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

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