絶対に解けるスライドパズルの作り方

ナンバーパズルを作るとき、最初に立ちはだかったのがこの問題でした。

15パズルの数字をランダムに並べ替えると、約半分の確率で絶対に解けない盤面ができます。

これは有名な事実です。全ての並び方のうち、完成形にたどり着けるのはちょうど半分だけ。19世紀にはこれを利用した懸賞パズルがあって、「絶対に解けない配置に賞金をかける」という商売が成立したという逸話も残っています。

ゲームとして、これは絶対に避けなければなりません。どれだけ考えても解けない盤面を出すのは、難易度ではなく欠陥です。

王道の解決策：偶奇性を計算する

この問題には教科書的な解法があります。盤面の転倒数（並び順がどれだけ入れ替わっているかの指標）と、空きマスの位置を組み合わせて、解けるかどうかを判定する式があるのです。

4×4の場合、おおまかにはこうなります。

数字の並びの転倒数を数える
空きマスが下から何行目にあるかを調べる
この2つの偶奇の組み合わせで、解けるか解けないかが決まる

判定式を書いて、解けない盤面が出たら作り直す。あるいは2つの数字を入れ替えて偶奇を反転させる。どちらも正しい方法です。

ただ、この方法には気になる点がありました。

3×3、4×4、5×5で条件が微妙に違います。 盤の幅が偶数か奇数かで、空きマスの行を考慮するかどうかが変わるのです。3つのサイズに対応するなら、それぞれ正しく実装して、それぞれ検証する必要があります。

そして偶奇性のバグは、発生してもすぐには気づけません。「解けない盤面が出た」ことに気づくには、実際に長時間解こうとして詰まる必要があります。テストで捕まえるのも簡単ではありません。

採った方法：完成形から逆に崩す

もっと単純で、確実な方法を選びました。

完成した状態から始めて、空きマスをランダムに動かす

それだけです。完成形から合法手だけを積み重ねて作った盤面は、その手順を逆にたどれば必ず完成形に戻れます。だから解けないはずがありません。

1. 1〜15を正しく並べ、右下を空きマスにする（完成形）
2. 空きマスの隣にあるパネルをランダムに1つ選び、スライドする
3. 2を規定回数くり返す

偶奇性の計算は一行も要りません。盤のサイズが変わっても、コードはそのままです。「解ける盤面の集合」を数学的に判定するのではなく、最初から解ける盤面しか作らないというアプローチです。

シャッフルの回数は、3×3で60手、4×4で140手、5×5で240手にしています。

「直前に戻る手」を禁止する

素朴に実装すると、ひとつ問題が起きます。

空きマスをランダムに動かすと、右に動かした直後に左に戻ることが頻繁に起きます。4方向のうち1つは必ず「さっき来た方向」なので、確率的にはかなりの割合です。これでは2手かけて何も混ざりません。

そこで、ひとつ前にいた位置には戻らないという制約を入れました。

const candidates = getNeighbors(empty, size).filter((i) => i !== prevEmpty);

たった1行ですが、効果は大きいものでした。空きマスが常に新しい場所へ進み続けるので、同じ手数でもはるかによく混ざります。

これは迷路を探索するときに来た道を戻らないのと同じ発想です。ランダムウォークに「後戻り禁止」を加えるだけで、探索範囲が一気に広がります。

それでも完成形に戻ってしまったら

確率は低いのですが、ランダムな手順がたまたま完成形に戻ってしまう可能性はゼロではありません。特に3×3の60手では、十分ありえます。

そのため、シャッフルの最後に完成しているかどうかを確認して、もし完成していたらもう1手だけ動かす処理を入れています。

if (isSolved(board)) {
  const candidates = getNeighbors(empty, size);
  const pick = candidates[0];
  board[empty] = board[pick];
  board[pick] = 0;
}

地味な処理ですが、「シャッフルしたのに最初から完成していた」という事故は、一度でも起きると台無しです。確率が低いことと、起きないことは違います。

この方法の欠点

正直に書いておくと、この方法には欠点があります。

盤面の難しさを制御できません。 判定式を使う方法なら「解くのに最低何手かかる盤面か」を計算して難易度を揃えられますが、ランダムウォークではそれができません。240手動かしても、たまたま完成形に近い盤面ができる可能性があります。

厳密に難易度を揃えたいなら、生成した盤面の最短手数を求めて、基準を満たさなければ作り直す、といった処理が必要になります。

ただ、このゲームではそこまでやりませんでした。スコアが手数と時間で決まるので、簡単な盤面が出たらそれは高得点のチャンスになるからです。難易度のばらつきが、そのまま「運の要素」として機能しています。

これが競技性の高いパズルなら、話は違ったと思います。どこまで作り込むかは、そのゲームが何を競っているかで決まります。

同じ考え方を他のゲームでも使っている

この「不正な状態を判定して弾くのではなく、正しい状態しか作らない」という発想は、他のゲームでも使っています。

ナンバーハントでは、25個の円が重ならないように配置する必要があります。ここでは「置いてみて、近すぎたら置き直す」という方法を取っていて、どうしても置けなければレイアウト全体を作り直します。

無限リバーシや無限ぽこぽこの不定形の盤面は、中央の2×2から外側へ1マスずつ広げて生成しています。この方法なら、飛び地ができることが原理的にありません。マスをランダムにばらまいて連結性を検査する、という方法もありますが、そもそも連結でないものを作らないほうが確実です。

「あとで検査する」より「最初から作らない」。バグの入り込む余地が減るぶん、こちらのほうが安心して寝られます。

実際の挙動はナンバーパズルで確かめてみてください。何度リセットしても、必ず解ける盤面が出ます。