スライドパズルを手で解く方法は一つです。盤面のサイズに依存しません。3×3でこれを習得すれば、4×4・5×5・6×6・それ以上のどんなサイズでも同じ方法が使えます。これがその方法です。
計画
N×Nのパズルに対して：
- 1行目を揃える — タイル1・2・…・Nを上段に配置する。
- 1列目を揃える — 1行目より下の左列にタイルN+1・2N+1・…を配置する。
- これで（N−1）×（N−1）のパズルになりました。 再帰する。
- ベースケース — 2×2になったとき、残りのタイルは揃っているか、偶奇性チェックが必要かのどちらか。
これがアルゴリズムの全体です。3文。残りは仕組みの話です。
仕組み：隅の操作
行や列の最初のタイルを置くのは簡単です。難しいのは最後のタイル——隅のタイル——を置くことです。
1行目の右上隅（N×NのパズルのタイルN）に対して：
- タイルNを直接隅にスライドしようとしない。そこには留まらない。
- まず前のタイル（タイルN−1）を隅に置く。
- タイルNをN−1の真下に置く。
- ペアを回転させる：空きマスを隅に移動し（N−1をどかして）、N−1を左下に逃がし、Nを上の隅に移動し、N−1を右にスライドする。
結果として、N−1とNが左側の配置を崩さずに正しい位置に収まります。
これがL字型の隅の操作です。同じ手筋を鏡像にすると1列目の左下隅でも使えます。
スライドパズルの技術を一つだけ覚えるとしたら、これを覚えてください。他のすべてはここから導かれます。
仕組み：中間タイル
行の中間（上段のタイル1からN−2まで）の配置は直接的です：
- 置きたいタイルを見つける。
- 目標位置の隣に移動させる。
- 空きマスを使って所定の位置にスライドさせる。
他の未配置のタイルを押しのける必要があるかもしれません。それは構いません——まだ配置されていないタイルだから。左側の配置済みタイルを崩さない限り、行はきれいに積み上がります。
安全を保つルール：空きマスを配置済みタイルを越えて動かさない。空きマスが盤面の右から配置済みタイルの左まで移動する必要がある場合、空きマスを未配置のマスを通じて配置済みタイルの周りを迂回させる必要があります。
「行、次に列」の理由
2つの理由があります：
- 鏡像対称性。 行の隅の操作と列の隅の操作はまったく同じ手筋を鏡像にしたものです。一方を学べばもう一方も習得できます。
- 空きマスに作業スペースがある。 1行目を解いた後、空きマスは下の（N−1）行で動き回れます。1列目を解いた後は（N−1）×（N−1）の領域があります。作業領域が適切に縮んでいきます。
交互にやる方法（1行目、1列目、2行目、2列目、…）もできますが、自然なリズムは外側でペアにして行い、再帰することです。
再帰
1行目と1列目が完成すると、残りの（N−1）×（N−1）パズルには別のゴール配置に入るタイルが残っています——同じ数字の順番ですが、位置が違います。良いニュース：この方法は気にしません。新しい上段を揃え、新しい左列を揃え、再帰する。最終的に2×2か3×3のベースケースに到達します。
3×3のベースケースでは、最後の3枚のタイルを繰り返し1手ずつ動かして揃えられます。2×2のベースケース（大きなパズルの最後に現れることがある）も同様です。
なぜどんなサイズでも機能するか
スライドパズルファミリーには便利な再帰的性質があります：行と列を解くことで、同じ種類のより小さいパズルになります。数学は単純です。1行目にN枚のタイルを置いた後（二度と触れないとして）、残りのゲームは1行欠けた（N−1）幅のグリッド上に存在します。左列を置いた後は（N−1）×（N−1）のグリッド上になります。
この還元をすべてのステップで適用できます。6×6は5×5に、5×5は4×4に、4×4は3×3の終盤に還元されます。3×3の終盤だけが特殊ケースの技術を持つ唯一のものです。それより大きいものはすべてそこに還元されます。
この再帰的構造が、スライドパズルがプログラミングコースで分割統治法の教材として使われる理由です。正しさの証明は1段落、実装はアルゴリズムの本体です。
どこまで速くなれるか
この方法を文字通り適用する初めての挑戦者にかかる時間：
各サイズを数回やると、これらの時間は半分になります。方法は同じで、隅の操作が運動記憶になるだけです。
この方法が向かないこと
最適解。 本物のソルバーを持つコンピュータは、行と列の手法が出す手順より30〜50%短い手順を見つけます。人間はそれらのアルゴリズムを頭の中で実行できません。
スピード解きの競技。 トップの速度解きをする人間は、行と列の手法を基礎として使いながら積極的に近道を切り、後で戻すための部分配置を行います。これは速いですが、習得が難しい。
それ以外の人——行と列の手法がその方法です。