置換逆数の数を求める

Question

私はthisを見ていました。私は15個のパズルソルバーを作ろうとしているからです。私はそれが何を言っているのか本当に理解していない。 "リストの置換シンボルが+1であれば、位置が可能である"と仮定すると、与えられた数の集合（0-15、配列に格納され、0は空白）が有効であるかどうかを調べるにはどうすればよいでしょうか？関連性があるならば、私はjavascriptで作業しています。

Answer 1

次のことを考慮してください：15パズルを解き、ブロックペアを物理的に取り外してスワップして交換した場合は、14と15ブロックを交換してスクランブルして有効な状態に戻せますか？

答えはノーです。あなたが15パズルで行うことができるすべての動きによって保存される不変量があり、置換記号は恐らくその不変量を指しています。 http://en.wikipedia.org/wiki/Fifteen_puzzleによれば

：

不変量は、全ての16乗（15個プラス空の正方形）の順列プラス空の正方形によって移動タクシー距離のパリティのパリティです。

これは不変であり、各移動によって、並べ替えのパリティとタキシカブ距離のパリティの両方が変更されるためです。特に、空の四角が移動しない場合、残りの部分の順列は偶数でなければならない。

（あなたはまた、レビ・チビタ記号をチェックアウトすることができますが、それは少し難解だ）、Pythonでそれを実装し、空の角はその開始から移動したマンハッタン距離を計算し、このパリティを計算http://en.wikipedia.org/wiki/Parity_of_a_permutationをチェックアウトしますこれらの値の合計のパリティを取ることができます。

ような何か：ここ

#!/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

これらのパズルのいずれかでピースを動かすために必要な「サイクル」のために、ピーススワップを単独で行うことはできません。ボードを考えてみましょう：

あなたはそれを解決するために（12）（11）を交換する必要があります。しかし、どうしたらいいですか？いずれかの方向に単に「サイクリング」（11,12,15、 - ）しても、順序が変わることはありません。したがって、より多くの部分を含める必要がありますが、そうすることで、他の部分の順序を維持することはできません。私たちが試してみると、他のペアがスワップされる順序になります。例えば、我々が関与することにより（12）（11）とを修正する可能性がある（7）及び（8）が、そうすることで、スワップ（8）及び（ - ）：

したがって

、パズルを解決するために必要なスワップの数が均等でなければならない、または上のボードのように「奇妙な人」が残っている。

したがって、ソルバーで単一のスワップがパズルを解く状況を検出した場合、このボードを解くことはできません。