スライドパズルの「解けない配置」はなぜ存在するのか

一手ごとに変わるもの：入れ替えの回数と空きマスの色

スライドパズルの一手は、空きマスと隣のタイル1枚の入れ替えです。空きマスを「0番のタイル」とみなすと、盤面は9枚（4×4なら16枚）の並べ替えの結果です。一手で入れ替えが1回だけ起きるので、並び方の偶奇（入れ替えの回数が偶数回で作れる並びか、奇数回で作れる並びか）は、一手ごとに必ず切り替わります。

もう一つ、見落としやすい事実があります。空きマスは一手で必ず上下左右の隣へ動きます。盤面を市松模様（チェッカー盤）のように塗り分けると、空きマスの色も一手ごとに必ず切り替わります。

この二つが同時に切り替わるので、次の関係が生まれます。

• 並びの偶奇と、空きマスが完成形の位置から見て同じ色かどうかは、一手動かしても関係が崩れません。
• 完成形では、並びは偶数で、空きマスは自分の定位置にあります。
• したがって、完成形から動かして作れる盤面は、必ずこの関係を満たします。

逆に、この関係を満たさない盤面は、何手動かしても完成形から作れません。それが「解けない配置」の正体です。14と15だけを入れ替えた盤面は、入れ替えがちょうど1回分なので並びが奇数で、空きマスは定位置にあります。関係が崩れているため、完成には届きません。

数えて見分ける：逆転数という道具

盤面ごとに色塗りと入れ替え回数を考えるのは大変なので、ふつうは「逆転数」で判定します。左上から右へ、次の段へと数字を読み、空きマスは飛ばして1列に並べます。その列の中で、大きい数字が小さい数字より先に出てくる組の個数が逆転数です。

3×3の具体例を2つ考えてみます。完成形は1〜8が順に並び、右下が空きマスだとします。

• 上段が3・1・2、中段が4・5・6、下段が7・8・空きの場合。読み取った列は3,1,2,4,5,6,7,8です。逆転は(3,1)と(3,2)の2組なので、偶数で解けます。
• 上段が1・2・3、中段が4・5・6、下段が8・7・空きの場合。列は1,2,3,4,5,6,8,7です。逆転は(8,7)の1組なので、奇数で解けません。

判定の規則は盤面の幅で変わります。

• 3×3（幅が奇数）、解ける条件（完成形で空きが右下の場合）：逆転数が偶数
• 4×4（幅が偶数）、解ける条件（完成形で空きが右下の場合）：逆転数に「空きマスの行（下から数えて1行目、2行目…）」を足した数が奇数

4×4では、タイルを上下に動かすと、1枚が3枚を飛び越えたのと同じ並びの変化が起きます。このため逆転数の偶奇が毎回切り替わり、空きマスの行も同時に1つ変わります。この二つを足すと、上下の動きでも偶奇が保たれます。左右の動きは列の順番を変えないので、何も変わりません。

14と15だけが入れ替わった4×4で確かめてみます。逆転数は1、空きマスは下から1行目で、足すと2です。奇数にならないので、解けない配置です。

自分で試せる最小のコードを置きます。HTMLファイルとして保存してブラウザで開くと動き、空きマスは0で入力します。完成形は1から順に並び、右下が空きマスという前提です。

<input id="b" size="40" value="1 2 3 4 5 6 8 7 0">
<button onclick="r.textContent=check(b.value)">判定</button>
<p id="r"></p>
<script>
function check(s){
  const a=s.trim().split(/\s+/).map(Number);
  const n=Math.round(Math.sqrt(a.length));
  if(n*n!==a.length) return "マスの数が正方形になっていません";
  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 row=n-Math.floor(a.indexOf(0)/n); // 下から数えた空きの行
  const ok = n%2===1 ? inv%2===0 : (inv+row)%2===1;
  return "逆転数 "+inv+(n%2===0?"、空きの行(下から) "+row:"")
    +" → "+(ok?"解ける配置":"解けない配置");
}
</script>

出題を「必ず解ける」にする二つの作り方

ゲームが解けない配置を出さないようにするには、大きく二つの方法があります。

一つ目は、完成形から出発して、規則どおりの手をランダムに何十手も動かす方法です。動かした先の盤面は、定義上、戻る道が必ずあります。偶奇の判定は不要です。

二つ目は、タイルを自由にシャッフルしてから逆転数などで判定し、解けないときは2枚を入れ替えるなどして偶奇を直す方法です。シャッフルの偏りが出にくい利点があります。

どちらの方法でも、結果として出る盤面は解ける側の半分に収まります。外から眺めて、どちらの方法かを見分けることはできません。

かたちのあいだの設計から読み取れること

「かたちのあいだ」は、数字を順にそろえるスライドパズルです。3×3の入門と、4×4の2段階が用意されています。確認済みの機能のうち、解ける配置の話に関わるものを挙げます。

• 次の一手のヒント：「最短とは限らない」と案内されています。ヒントが「次に動かす一手」を示す以上、その盤面から完成まで進める道があることが前提と読み取れます。
• 一手戻す：手数は減らないとされています。戻す操作は直前の動きを逆にするだけなので、盤面の偶奇には影響しません。解ける側の盤面は解ける側のままです。
• 同じ配置の再挑戦：出題された盤面をそのままやり直せます。解ける盤面を作る仕組みの結果が、再挑戦でも再現される形です。
• 時計の一時停止と保存：盤面そのものは変わらないため、偶奇にも関係しません。

一方、出題が先ほどの二つの作り方のどちらなのか、完成形の空きマスがどこにあるのかは、確認済みの情報にありません。この部分は作品を開いて確かめてください。ヒントの存在は解ける配置であることの傍証にはなりますが、仕組みの証明にはなりません。

自分で確かめる設計書

次の問いを立てます。「かたちのあいだが出す開始盤面は、すべて逆転数の規則を満たしているか」。

準備するもの

• 作品を開いたブラウザ
• 紙とペン、または上のコードを保存したHTML

手順

1. 作品を開き、完成形の数字の並びと空きマスの位置を確かめます。右下以外なら、規則の「空きマスの行」の数え方を作品の完成形に合わせて変えます。
2. 3×3の入門で新しく始め、最初の盤面を左上から右へ、次の段へと読み取って書き留めます。空きマスは0とします。
3. 逆転数を数えて偶奇を記録します。コードに貼って照合しても構いません。
4. 3×3で10回、4×4で10回、これを繰り返します。4×4では空きマスの行も記録します。
5. 記録の単位は「1回の開始盤面につき1行」です。盤面、逆転数、判定結果を書きます。

結果の読み方

• すべての行が解ける側なら、出題はこの規則と矛盾しません。20回では「必ず」の証明にはなりません。
• 解けない判定が出たら、まず読み取りミスを疑います。タイルの数え間違い、空きマスを数に含めた、完成形の空き位置が右下ではなかった、のいずれかが典型です。
• 読み取りを見直しても解けない判定が残る場合は、規則の前提（完成形の並び）が作品と違う可能性があります。完成形を確かめ直してください。

起こりやすい誤り

• 空きマスを逆転数に含めてしまうこと
• 縦の列順に読んでしまうこと
• 4×4で、空きマスの行を上から数えてしまうこと

次の行動

まず、かたちのあいだの3×3入門を開き、最初に出た盤面の逆転数を数えてみてください。偶数になっていれば、規則どおりに解ける側の盤面です。そのうえで、一手動かすたびに逆転数がどう変わるかを追うと、偶奇が保たれる理由を実感できます。