スライドパズル4×4の配置の数と、解ける配置の割合

配置の数を数える

4×4の盤には16個のマスがあり、15枚のタイルと1つの空きを置きます。空きも「1つの駒」とみなすと、16個のものを16マスに並べる並べ方の数になります。

• 最初のマスに置けるものは16通りです。
• 次のマスは残りの15通り、その次は14通りです。
• これを最後まで掛けた16!（16の階乗）が総数です。

16! = 20,922,789,888,000（約20.9兆）です。盤の大きさ別に並べると次のとおりです。

• 2×2、総配置数：24、その半分：12
• 3×3、総配置数：362,880、その半分：181,440
• 4×4、総配置数：20,922,789,888,000、その半分：10,461,394,944,000

「半分」の欄は、次の節以降で確かめる主張です。ここで押さえておくのは総数のほうです。

解ける配置を見分ける印

配置を見て、解けるかどうかを一瞬で判定する方法があります。ゴールを「1から15が左上から読み順に並び、空きが右下」とした場合の手順です。

1. 空きを除いた15枚を、左上から右へ、次の段へと読み順に並べて数列にします。
2. その数列で、前にある数のほうが後ろにある数より大きい組を数えます。これを転倒数と呼び、ここではNと書きます。
3. 空きが下から数えて何段目かを調べます。最下段が1、最上段が4で、これをrと書きます。
4. N＋rが奇数なら解けます。偶数なら、どう動かしても揃いません。

ゴールで確認します。Nは0、空きは最下段なのでr＝1です。合計は1で奇数、解ける側です。

有名な「14と15だけ入れ替えた配置」を考えてみます。最下段が「13・15・14・空き」で、ほかはゴールどおりです。数列は1から13、15、14の順で、逆転しているのは「15と14」の1組だけなのでN＝1です。r＝1なので合計は2で偶数となり、解けない側だと分かります。

解ける側の例も作ります。ゴールから、空きの上にある12を下へ1回スライドさせます。3段目は「9・10・11・空き」、4段目は「13・14・15・12」になります。数列の末尾が13、14、15、12なので、逆転は「13と12」「14と12」「15と12」の3組で、N＝3です。空きは下から2段目なのでr＝2、合計は5で奇数です。実際に1手で作った配置ですから、解ける側という判定と合っています。

なぜ偶奇が変わらないのか

この印が正しい理由は、1手動かしたときにN＋rの偶奇が変わらないことです。動きは2種類しかありません。

• 横に動かす場合：タイルは同じ段の中で動くだけです。読み順の数列は変わらないのでNは同じで、空きの段も同じなのでrも同じです。
• 縦に動かす場合：動くタイルは、読み順で3枚ぶんを飛び越えます。4×4では1段が4マスなので、間に挟まるタイルが3枚になります。この3枚との大小関係が1組ずつ反転するため、Nの変化は±1か±3のどちらかで、必ず奇数です。同時に空きが1段動くので、rは±1変わります。奇数と奇数の変化が重なって、合計の偶奇は元に戻ります。

つまりN＋rの偶奇は、どんな手順でも保たれる「保存量」です。ゴールは奇数なので、偶数の配置には永久に行き着けません。

半分ちょうどになる理由

偶奇が合わない配置は解けないと分かりました。次の問いは、偶奇が合う配置がちょうど半分あることです。

1つ目は、ペアを作る見方です。空き以外の好きな2枚を取り替えると、数列の転倒数の偶奇が必ず変わります（2つの値の入れ替えは偶奇を反転させる性質があります）。空きの位置は動かないのでrは同じです。そのため、取り替えによって「解ける側」と「解けない側」が1対1に対応し、どちらも総数のちょうど半分になります。

2つ目は、偶奇が合う配置にはすべて到達できるか、という点です。これは19世紀から知られている定理で、4×4では偶奇が合う配置はすべて、動かして揃えられます。この記事では証明を追わず、次の節で小さな盤を使って実際に確かめます。

自分で確かめる二つの方法

小さな盤を全部数える

2×2と3×3は、ゴールから1手ずつ動かして到達できる配置を全部集められます。ブラウザの開発者ツールのコンソールに貼って動かしてみます。

function reach(w){
  const n = w*w;
  const goal = [...Array(n).keys()].map(i => (i+1)%n); // 1,2,...,0(空き)
  const seen = new Set([goal.join(",")]);
  let queue = [goal];
  while(queue.length){
    const next = [];
    for(const s of queue){
      const b = s.indexOf(0), r = Math.floor(b/w), c = b%w;
      for(const [dr,dc] of [[1,0],[-1,0],[0,1],[0,-1]]){
        const nr = r+dr, nc = c+dc;
        if(nr<0 || nr>=w || nc<0 || nc>=w) continue;
        const t = s.slice(), j = nr*w+nc;
        [t[b],t[j]] = [t[j],t[b]];
        const k = t.join(",");
        if(!seen.has(k)){ seen.add(k); next.push(t); }
      }
    }
    queue = next;
  }
  return seen.size;
}
for(const w of [2,3]) console.log(w+"×"+w, reach(w));

出てきた数を、前の表の「その半分」の欄（2×2は12、3×3は181,440）と見比べます。一致すれば、小さな盤では「偶奇が合うものは全部届く」ことを数で確認できたことになります。4×4にこのコードを使うのはやめてください。配置が10兆を超えるため、ブラウザのメモリでは終わりません。

4×4を無作為に並べて割合を見る

4×4は、並べ替えをでたらめに作り、先ほどの印で判定して割合を数えます。

function solvable(a){ // 0が空き。ゴールは1..15が読み順で空きが右下
  const t = a.filter(x => x>0);
  let inv = 0;
  for(let i=0;i<t.length;i++) for(let j=i+1;j<t.length;j++) if(t[i]>t[j]) inv++;
  const r = 4 - Math.floor(a.indexOf(0)/4); // 下から数えた空きの段
  return (inv + r) % 2 === 1;
}
function shuffle(a){
  for(let i=a.length-1;i>0;i--){
    const j = Math.floor(Math.random()*(i+1));
    [a[i],a[j]] = [a[j],a[i]];
  }
  return a;
}
let ok = 0; const N = 1000;
for(let k=0;k<N;k++) if(solvable(shuffle([...Array(16).keys()]))) ok++;
console.log(ok + " / " + N);

実行を何回か繰り返して、「解ける」の個数を紙に書き留めます。1回ごとの値はばらつくので、1回の結果で判断しないことが大切です。

• 記録の単位：1回の実行が1行で、1000個中の「解ける」の個数を書きます。
• 回数：10回以上が目安です。
• 読み方：公平なコインを1000回投げた場合、表の数はおおよそ470〜530の範囲に入ることが多くなります。結果がこの範囲に集まり、平均が500付近なら「半分」と矛盾しません。400や600に偏るなら、コードの写し間違いか、シャッフルの書き方を疑います。

起こりやすい誤りと、作品での使い方

• 空きを数列に入れてしまう：転倒数には空きを含めません。
• rの数え方が逆：上から数えると判定が逆になります。下から数えます。
• ゴールの形が違う：この印は「空きが右下」のゴールを前提にしています。空きがほかの位置のゴールには、そのまま使えません。
• シャッフルの偏り：配列の並べ替えに sort(() => Math.random() - 0.5) を使うと偏ります。上のコードのように、末尾から入れ替える方法を使います。

アソバースの公式作品「かたちのあいだ」には、3×3の入門と4×4の2段階があり、同じ配置の再挑戦ができます。遊ぶ前の配置を紙に写し、ゴールの空きの位置を作品で確かめたうえで、この記事の印を当てはめることもできます。作品が配置をどのように作っているかは確認済みの情報にないため、画面を開いて確かめてください。

次の行動

まずは2×2と3×3のコードを実行し、出てきた数が表の「半分」の欄と合うかを見てください。次に4×4の無作為抽出を10回以上繰り返して、「解ける」の個数を書き留めます。最後に、手元のスライドパズルの配置を1つ選び、転倒数と空きの段を数えて、解けるかどうかを先に予想してみてください。