パズルが解けるかどうかを先に判定する：転倒数の数え方

転倒数の数え方：盤を一列に読み下す

手順は3つです。

1. 盤を左上から右へ、上の段から下の段へ読み、数字を一列に並べます。
2. 空白は列から取り除きます。
3. 列の中で「前にある数のほうが後ろにある数より大きい」組の個数を数えます。これが転倒数です。

次の3×3の配置で数えてみます。空白は「＿」と書きます。

• 1段目：8、1、2
• 2段目：＿、4、3
• 3段目：7、6、5

空白を除いて読むと、8、1、2、4、3、7、6、5 の8個です。左から順に、その数より後ろにある小さい数の個数を数えます。

• 8、後ろにある、それより小さい数：1、2、4、3、7、6、5、個数：7
• 1、後ろにある、それより小さい数：なし、個数：0
• 2、後ろにある、それより小さい数：なし、個数：0
• 4、後ろにある、それより小さい数：3、個数：1
• 3、後ろにある、それより小さい数：なし、個数：0
• 7、後ろにある、それより小さい数：6、5、個数：2
• 6、後ろにある、それより小さい数：5、個数：1
• 5、後ろにある、それより小さい数：なし、個数：0

合計は 7＋1＋2＋1＝11 です。この偶奇（偶数か奇数か）が判定に使われます。数えるのは偶奇だけなので、11か13かといった違いは気にしなくて構いません。

3×3の判定：転倒数が偶数なら解ける

この記事では、完成形を「1から順に左上から並べ、空白が右下」とします。この前提は後でもう一度確認します。

盤の幅が奇数（3×3や5×5）のときの条件は簡単です。

• 転倒数が偶数なら、解けます。
• 転倒数が奇数なら、解けません。

先ほどの配置は転倒数が11で奇数なので、解けない配置です。ほかの例も見ておきます。

• 1、2、3 / 4、5、6 / 7、＿、8：読み下すと1から8が順に並び、転倒数は0（偶数）です。8を左へ動かせば完成するので、解けます。
• 1、2、3 / 4、5、6 / 8、7、＿：転倒数は、8が7より前にある1組だけで1（奇数）です。7と8だけが入れ替わった配置で、解けません。

4×4の判定：空白の行も数える

幅が偶数（4×4）のときは、転倒数だけでは決まりません。空白が下から何段目にあるかも使います。下の段を1段目として数えます。

• 転倒数と、空白がある段（下から数えた番号）を足して、奇数なら解けます。
• 偶数なら、解けません。

例を2つ見てみます。

• 1〜12は順に並び、最下段が13、15、14、＿の配置：転倒数は 15 と 14 の1組で1です。空白は最下段（1段目）なので、足すと2で偶数になり、解けません。
• 1〜11が順に並び、3段目が9、10、11、＿、最下段が13、14、15、12の配置：12より前に13、14、15があるので転倒数は3です。空白は下から2段目なので、足すと5で奇数になり、解けます。実際に、12を1つ上へ動かすだけで完成します。

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

この判定がなぜ成り立つかを知っておくと、別の盤サイズにも応用できます。駒を動かす操作は、空白と隣の駒を入れ替えることだけです。その前後で、転倒数の偶奇がどう動くかを見ます。

• 左右の移動：空白を取り除いた列で、駒の並び順は変わりません。転倒数はそのままです。
• 上下の移動：駒は列の中で、幅 N の分だけ離れた位置へ動きます。間にあるのは空白ではない N−1 個の駒で、その1個ごとに大小の順序が入れ替わります。転倒数はそのたびに1増えるか1減るかするので、変化の偶奇は N−1 と同じです。

幅が3なら N−1 は2で、上下に動いても転倒数の偶奇は変わりません。だから「偶数なら偶数のまま」という条件だけで足ります。

幅が4なら N−1 は3で、上下に動くたびに転倒数の偶奇が入れ替わります。同時に、空白の段も1つ上か下に動きます。偶奇が入れ替わる動きと、段の番号が1つ変わる動きが同時に起きるので、足し算の偶奇は保たれます。

完成形は、転倒数が0で空白が最下段にあります。3×3なら転倒数は偶数、4×4なら転倒数と段番号の和は奇数です。解ける配置は、動かしても必ずこの性質を保ちます。逆に、この性質を満たす配置はすべて完成形へたどり着けることも、よく知られた結果です。ここでは証明を省き、性質が保たれることだけを押さえておきます。

コードで確かめる

判定を関数にしたものです。空白は 0 で表し、盤は一次元の配列で渡します。ブラウザのコンソールか Node.js でそのまま動きます。

function countInversions(tiles) {
  let count = 0;
  for (let i = 0; i < tiles.length; i++) {
    if (tiles[i] === 0) continue;
    for (let j = i + 1; j < tiles.length; j++) {
      if (tiles[j] !== 0 && tiles[i] > tiles[j]) count++;
    }
  }
  return count;
}

function isSolvable(tiles, width) {
  const inv = countInversions(tiles);
  if (width % 2 === 1) return inv % 2 === 0;
  const row = Math.floor(tiles.indexOf(0) / width); // 上から0始まり
  const rowFromBottom = width - row;                // 下から1始まり
  return (inv + rowFromBottom) % 2 === 1;
}

function shuffleByMoves(width, steps) {
  const n = width * width;
  const t = [...Array(n - 1)].map((_, i) => i + 1).concat(0);
  let b = n - 1;
  for (let s = 0; s < steps; s++) {
    const x = b % width, y = Math.floor(b / width);
    const nb = [];
    if (x > 0) nb.push(b - 1);
    if (x < width - 1) nb.push(b + 1);
    if (y > 0) nb.push(b - width);
    if (y < width - 1) nb.push(b + width);
    const to = nb[Math.floor(Math.random() * nb.length)];
    [t[b], t[to]] = [t[to], t[b]];
    b = to;
  }
  return t;
}

console.log(isSolvable([1,2,3,4,5,6,8,7,0], 3));   // false
console.log(isSolvable([8,1,2,0,4,3,7,6,5], 3));   // false（転倒数11）
console.log(isSolvable([1,2,3,4,5,6,7,0,8], 3));   // true
console.log(isSolvable([1,2,3,4,5,6,7,8,9,10,11,0,13,14,15,12], 4)); // true
for (let k = 0; k < 1000; k++) {
  if (!isSolvable(shuffleByMoves(4, 60), 4)) console.log("矛盾", k);
}

最後のループは、完成形から合法手だけで混ぜた配置を1000個作り、すべてが「解ける」と判定されるかを調べます。「矛盾」と表示されなければ、判定が手の動きと食い違っていないことになります。表示が出たら、完成形の前提（空白の位置）や段の数え方を見直してください。

出題の設計：二つの作り方と、確かめたい点

解ける配置を出題する方法は、大きく二つあります。

• 合法手で混ぜる方法：完成形から実際に駒を動かして混ぜます。動かした結果なので、必ず解けます。上のコードの shuffleByMoves がこれです。偏りを減らすには、手数を十分に取り、直前の手を打ち消す動きを避けるとよいです。
• 並べ替えて判定する方法：数字をでたらめに並べ、isSolvable が偽なら作り直します。どの配置も等しい確率で出せますが、半分は捨てることになります。

どちらを選んでも、「完成形に近すぎる配置が出る」問題は別に残ります。混ぜる手数が少なすぎる場合は、解ける配置でも数手で終わってしまいます。判定は「解けるか」しか答えず、「どれだけ難しいか」は教えてくれません。

公式作品の「かたちのあいだ」は、数字を順にそろえるスライドパズルで、3×3の入門と4×4の2段階があります。確認済みの機能は、次の一手のヒント（最短とは限らない）、一手戻す（手数は減らない）、同じ配置の再挑戦、時計の一時停止、保存です。ここから読み取れることは次のとおりです。

• 「同じ配置の再挑戦」があるので、出題された配置を保持し、最初から並べ直せる作りになっています。
• 一手戻しても手数が減らない設計なので、手数は「やり直しを含めた操作の量」を表すものと考えられます。
• ヒントが最短手を保証しないと明記されているので、ヒントの目的は最短解の提示ではなく、次に進む手がかりを渡すことだと読めます。

どの方法で配置を作っているか、完成形で空白がどこにあるかは、確認済みの情報にありません。この部分は作品を開いて確かめてください。

確かめ方の一例です。作品を開いて、最初に出た配置を紙に写します。上の手順で転倒数を数え、3×3なら偶数か、4×4なら空白の段と合わせて奇数かを見ます。合っていれば、完成形が「空白が右下」という前提とも一致します。合っていない場合は、完成形の空白の位置が違うか、数え間違いのどちらかです。完成形を実際に確かめたうえで、条件を組み替えて照らし合わせてください。

次の行動

自作のスライドパズルがあれば、出題する配置に isSolvable を通して、偽になるものがないかを確かめてください。まだ作っていない場合は、まず3×3で「合法手で混ぜる」方式を実装し、判定関数を検算に使うところから始めるのがおすすめです。

「かたちのあいだ」で出た配置を写し、転倒数を手で数える練習もしておくと、判定の感覚がつかめます。