Блог

Я рассматривал это, потому что пытаюсь создать решатель пятнадцати головоломок. Я действительно не понимаю, о чем это говорит. Как бы я проверил, является ли заданный набор чисел (от 0 до 15, хранящихся в массиве, 0 является пустым) допустимым, учитывая, что «если символ перестановки в списке равен 1, позиция возможна». Я работаю на javascript, если это уместно.

Подумайте о следующем: если бы вы взяли решенную головоломку из 15 элементов и с помощью пары плоскогубцев физически удалили и поменяли местами блоки 14 и 15 и скремблировали ее … могли бы вы вернуть ее в допустимое состояние?

Ответ отрицательный. Существует инвариант, который сохраняется всеми ходами, которые вы можете выполнить в головоломке из 15 элементов, и символ перестановки, вероятно, ссылается на этот инвариант.

Согласно http://en.wikipedia.org/wiki/Fifteen_puzzle :

Инвариантом является четность перестановки всех 16 квадратов (15 штук плюс пустой квадрат) плюс четность расстояния, пройденного такси пустым квадратом.

Это инвариант, потому что каждый ход изменяет как четность перестановки, так и четность расстояния до такси. В частности, если пустой квадрат не перемещен, перестановка оставшихся частей должна быть четной.

Чтобы вычислить это соотношение, ознакомьтесь с http://en.wikipedia.org/wiki/Parity_of_a_permutation (вы также могли бы проверить символ Леви-Чивиты, но это немного непонятно), реализуйте его на python, затем вычислите расстояние по манхэттену, на которое пустой квадрат переместился из своей начальной позиции, и возьмите четность суммы обоих этих значений.

Что-то вроде:

 #!/usr/bin/python3

from pprint import pprint

state_starting = list(range(1,16))   [None]
START = state_starting

def positionIsPossible(state):
    """
        state is a list, the starting position is [1,2,3,...,15,None]
    """
    numInversions = sum(
        state.index(START[j]) > state.index(START[i])
        for i in range(16) for j in range(i)  # each pair (i,j)
    )  #sum([True,True,False])==2

    # Uncomment if you want to see what's going on here:
    #pprint(list(
    #    ((i,j), (START[i],START[j]), state.index(START[j]) > state.index(START[i]))
    #    for i in range(15) for j in range(i)
    #))

    newEmptySquareYPos = state.index(None)//4
    newEmptySquareXPos = state.index(None)%4
    emptySquareMovedDistance = abs(3-newEmptySquareYPos) abs(3-newEmptySquareXPos)

    parity = (numInversions   emptySquareMovedDistance)%2

    print('number of inversions:', numInversions)
    print('distance empty square moved:', emptySquareMovedDistance)
    print('parity:', parity)

    return parity==0
  

Вот несколько примеров / тестовых примеров:

 def swap(state, i, j):
    state = list(state)
    state[i], state[j] = (state[j], state[i])
    return state

def validate(state):
    def formatState(state):
        return 'n'.join('|' ' '.join([str(y if y else '').rjust(2) for y in x]) '|' for x in [state[0:4],state[4:8],state[8:12],state[12:16]])
    print(formatState(state))
    print(state, 'is', 'reachable' if positionIsPossible(state) else 'unreachable')
    print()

# reachable
validate(state_starting)
validate(swap(state_starting, 15,14))
validate(swap(state_starting, 15,11))

# unreachable
validate(swap(state_starting, 14,13))
  

Результаты:

 | 1  2  3  4|                                                                                                                                                                                                                                                       
| 5  6  7  8|
| 9 10 11 12|
|13 14 15   |
number of inversions: 0
distance empty square moved: 0
parity: 0
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, None] is reachable

| 1  2  3  4|
| 5  6  7  8|
| 9 10 11 12|
|13 14    15|
number of inversions: 1
distance empty square moved: 1
parity: 0
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, None, 15] is reachable

| 1  2  3  4|
| 5  6  7  8|
| 9 10 11   |
|13 14 15 12|
number of inversions: 7
distance empty square moved: 1
parity: 0
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, None, 13, 14, 15, 12] is reachable

| 1  2  3  4|
| 5  6  7  8|
| 9 10 11 12|
|13 15 14   |
number of inversions: 1
distance empty square moved: 0
parity: 1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, None] is unreachable
  

Если ваш алгоритм на самом деле не заботится о том, возможна позиция или нет (вы просто делаете это, чтобы сказать «недопустимый ввод! установить невозможно!» вы могли бы проигнорировать эту часть, запустить ее в любом случае в течение нескольких сотен итераций и вернуть «невозможно!», если не решена.

Из-за «циклов», необходимых для перемещения фигур в одной из этих головоломок, замена фигур не может быть выполнена изолированно. Рассмотрим доску:

Вы должны поменять местами (11) и (12), чтобы решить эту проблему. Но как вы можете? Просто «циклирование» (11, 12, 15, -) в любом направлении порядок никогда не изменится. Поэтому мы должны задействовать больше фрагментов, но при этом мы не можем сохранить порядок расположения этих других фрагментов. Все, что мы пытаемся, приведет к порядку замены другой пары. Например, мы могли бы исправить (11) и (12), включив (7) и (8), но при этом поменяем местами (8) и (-):

Следовательно, количество замен, требуемых для решения головоломки, должно быть четным, иначе мы останемся с «нечетным игроком», как на доске выше.

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