3 x2スライディングパズル
このようなスライディングパズルを解くことは可能でしょうか（xはスペースです）?:
1 3 2
4 5 x
私はこれを解決することができず、それが可能かどうかさえわかりません。
回答
解決：
いいえ、「解決済み」パズルに与えた位置から取得することはできません $1,2,3,4,5$正しい順序で、右下のギャップ。これは、オリジナルの（有名な）「14,15パズル」と同じ方法で証明できます。
ここにある証明と同様に、いくつかの基本的な群論を使用して示すことができます。
パズルの各位置は、次の順列として解釈できます。 $\{1,2,3,4,5,6\}$、空白の正方形は次のように解釈されます $6$。パズルの各動きは、対称群の転置として解釈できます。$S_6$、空白の正方形を交換します $6$実際のタイルの1つで。あなたが与えた位置は、解決された位置から1転置されていますが、偶数の位置にしか到達できませんでした$6$-スワップ、その空白の正方形以来 $6$最終的には同じ位置にある必要があるため、上下の動きが偶数回、左右の動きが偶数回ある必要があります。ただし、偶数の転置の任意の組み合わせは、交代群に含まれている必要があります$A_6$、したがって、このような組み合わせでは単一の転置に到達することはできません。
あなたの目標が最初の行で「123」、2番目の行で「4 5 x」を取得することである場合、答えはノーです、それは不可能です。
これは、サムロイドの14-15パズルの小さいバージョンです。空のスペースが1つあるスライディングパズルがある場合は、パリティ（ソリューションに到達するために必要なスイッチの数）に基づいて解決できるかどうかを確認できます。具体的には：
- まず、空のタイルが正しい場所にくるように移動します。
- ここで、魔法のように2つのタイルを選択して位置を入れ替えることができると想像してください。パズルを解くのに何回の交換が必要ですか？
スワップの数が偶数の場合、元のパズルは解けます。スワップの数が奇数の場合、元のパズルは解けません。（言い換えれば、解決されたパズルから始めて、どんな動きをしても、常に偶数の場合になります-タイルをスライドさせるだけで2つのケース間をジャンプする方法はありません。タイル張り。）
あなたの例では、パズルを解くために必要なスワップは1つだけです。そのため、スライドで解決することはできません。