查找排列反转的数量

Question

我正在查看这个，因为我正在尝试制作一个十五个谜题求解器。我实在不明白它在说什么。考虑到“如果列表的排列符号是+1，则位置是可能的”，我将如何检查给定的一组数字（从0到15，存储在数组中，0是空白）是否有效。我正在使用 javascript（如果相关的话）。

Answer 1

考虑以下情况：如果您解决了一个 15 谜题，并用物理方式移除并交换了一对夹板，并替换了 14 和 15 块，并将其打乱。 .你能把它恢复到有效状态吗？

答案是否定的。在 15 个谜题中，您可以执行的所有移动都会保留一个不变量，并且排列符号可能指的是该不变量。

根据 http://en.wikipedia.org/wiki/Fifteen_puzzle ：

不变量是所有 16 个方格（15 块加空方格）的排列奇偶性加上空方格移动的出租车距离的奇偶性。

这是一个不变量，因为每次移动都会改变排列的奇偶性和出租车距离的奇偶性。特别是如果空方块没有移动，则剩余棋子的排列必须是偶数。

要计算此奇偶校验，请查看 http://en.wikipedia.org/wiki/Parity_of_a_permutation (你也可以查看 Levi-Civita Symbol，但它有点神秘），用 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

如果您的算法并不真正关心该位置是否可能（您只是这样做是为了说“无效输入！位置不可能！”您可以忽略这部分，无论如何运行数百次迭代，如果未解决则返回“不可能！”

Answer 2

由于移动这些拼图之一上的棋子需要“循环”，因此不能单独进行棋子交换。考虑董事会：

您必须交换 (11) 和 (12) 来解决它。但你怎么能呢？简单地向任一方向“循环”（11、12、15、-）永远不会改变顺序。因此，我们必须涉及更多的部分，但这样做时，我们无法保留其他部分的顺序。我们尝试的任何操作都会导致另一对的顺序被交换。例如，我们可以通过涉及 (7) 和 (8) 来纠正 (11) 和 (12)，但这样做时，交换 (8) 和 (-)：

因此，解决难题所需的交换次数必须是偶数，否则我们就会像上面的棋盘一样留下“奇怪的人”。

因此，如果您在解算器中检测到一次交换即可解决难题的情况，您就知道该板无法解决。