GODRICH
#cssアニメーション#ボタン#ローディング#トランジション#スクロール#ダッシュボード#実用ui#デザイントレンド

スライドパズル 9種 — 解ける盤の見分け方から最短手の探索まで

· Godrich · 9種 · 14分で読める

game素のJSSCSS自動再生ゲーム・遊びヒーロー

スライドパズルはなぜ解けない盤があるのでしょうか。02番はひっくり返った組の数で解ける盤を分け、05番はマンハッタン距離の上限を引き上げながら最短手を探し、07番はタイルをドラッグして離した位置でマスに吸いつけます。

スライドパズルは番号のタイルをやみくもに並べ替えるゲームではなく、空きマスの隣のタイルが入れ替わる規則のもとで、解ける盤と解けない盤が分かれる計算です — スライドパズルを作るには、混ぜ方と判定に使う値を決めることから始まります

空きマスへ列ごと動くタイルの連鎖01 sp-row-chain-slide ひっくり返った組の数で解ける盤を分ける02 sp-parity-solvable-check 元の位置までの距離を色で塗るマンハッタンのヒートマップ03 sp-manhattan-heat-map 完成した盤から歩いて出る混ぜ方04 sp-legal-walk-shuffle 上限を引き上げながら最短手を探す反復深化探索05 sp-ida-star-solve 一枚の絵をタイルに切って継ぎ目が見える盤06 sp-image-tile-cut ドラッグして離すとマスに吸いつくポインター07 sp-drag-clamp-snap 取り消しの記録と解法の再生08 sp-undo-replay-cancel 盤の大きさごとの状態数と探索ノードの比較09 sp-size-state-count-ramp

自動再生 · タイルを押すとその項目へ · すべて1つのzip

九つの場面は同じ盤の配列を共有し、場面ごとに違うのは値を読む関数だけです。盤を番号の配列として見れば、パズルは状態ひとつで、押したり動かしたりする画面はその状態を塗る作業にすぎません。

盤の状態は実際のパズルの処理からだけ作ります

九つの場面のどれにも、盤の配列をまねた絵を別に描くところはありません。bd 配列は rowChain・walkMoves・idaStar のような実際の移動の関数でだけ書き換え、画面は書き換わった配列をマスの座標に移して描きます。

一歩は1/60秒で固定し、乱数は整数のハッシュにします

経過時間は DT_MAX の0.05秒で切って積み、STEP_S の1/60秒ごとに分けて消化します。乱数は使わず、混ぜ方も場面の選び方も整数のハッシュ hash2(a, b) で決めるので、同じ種なら同じ盤、同じデモになります。タブが隠れるあいだはループを止め、戻ったら積んだ時間を捨てます。

        const order = [];
        for (let k = 0; k < list.length; k += 1) {
            order[list[k]] = k;
        }
        retarget(function (v) {
            const o = order[v];
            return (o ? o : 0) * STAGGER_MS / 1000;
        }, SLIDE_MS / 1000);
        recordPress(list, i);
    }

上のコードは01で使う開始時刻のずらしで、order に押した順の番号を入れ、STAGGER_MS の分だけ遅らせて retarget に渡します。

スライドパズル 9種 — 列ごとの移動・解ける盤の見分け方・マンハッタン距離のヒートマップ・歩いて混ぜる・最短手の探索・絵のタイルの切り出し・ドラッグして吸着・取り消しと解法の再生・盤の大きさごとの状態数

九つの場面を描画して測った面積とフレーム

場面 累積面積 動いたフレーム 強さの平均
01 列ごとの移動 27.1% 23/23 97.9
02 盤の見分け方 23.4% 22/23 120.5
03 マンハッタンのヒートマップ 18.9% 23/23 154.4
04 歩いて混ぜる 27.6% 23/23 119.9
05 最短手の探索 26.8% 22/23 126.0
06 絵のタイル 32.7% 21/23 106.1
07 ドラッグして吸着 12.7% 19/23 110.3
08 取り消しと再生 14.8% 21/23 153.0
09 状態数の比較 12.9% 21/23 143.8

累積面積が最も広いのは06の32.7%で、最も狭いのは07の12.7%です。動いたフレームは07が19/23で最少、01・03・04の三場面が23/23で、強さの平均は03の154.4が最高です。

01空きマスへ列ごと動くタイルの連鎖

空きマスと同じ列のタイルを押すと、その間のタイルが一マスずつ空きマスのほうへ動くので、一回の入力で何枚も動かしたいときに使えます。タイルごとに SLIDE_MS の140msで動き、始まりは STAGGER_MS の30msずつずれて順に付いていき、配列の入れ替えが先に終わるので、押した瞬間に盤の状態は決まっています。

空きマスへ列ごと動くタイルの連鎖
新しいタブで開く

01 · 空きマスへ列ごと動くタイルの連鎖 — 計測 累積面積 27.141% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

SLIDE_MSSTAGGER_MSrowChain
    function rowChain(b, n, i) {
        const z = b.indexOf(0);
        if (i === z) {
            return [];
        }
        let step = 0;
        if (Math.floor(i / n) === Math.floor(z / n)) {
            step = i > z ? 1 : -1;
        }
        else if (i % n === z % n) {
            step = i > z ? n : -n;
        }
        else {
            return [];
        }
        const moved = [];
        for (let p = z; p !== i; p += step) {
            b[p] = b[p + step];
            moved.push(b[p]);
        }
        b[i] = 0;
        return moved;
    }

rowChain が返した動いたタイルの順に開始時刻をずらすので、三枚を押すと最後のタイルが動き終わるまでは SLIDE_MS + 2 × STAGGER_MS で200msです。

02ひっくり返った組の数で解ける盤を分ける

タイルの番号を一列に並べ、前の番号が後ろの番号より大きい組(逆転)の数を数えると、4×4の盤では逆転の数と空きマスが下から何行目かの合計が奇数のときだけ解けます。この判定を実行して確かめたところ、3×3の完成盤から幅優先探索で行き着く181,440の盤はどれも solvable が真で、二枚だけ入れ替えた盤から行き着く181,440はどれも偽、二つの集合の重なりは0でした。

ひっくり返った組の数で解ける盤を分ける
新しいタブで開く

02 · ひっくり返った組の数で解ける盤を分ける — 計測 累積面積 23.449% · 動いたフレーム 22/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

inversionsparityblankRow
    function inversions(b) {
        let c = 0;
        for (let i = 0; i < b.length; i += 1) {
            for (let j = i + 1; j < b.length; j += 1) {
                if (b[i] !== 0 && b[j] !== 0 && b[i] > b[j]) {
                    c += 1;
                }
            }
        }
        return c;
    }
    // 空きマスが下から何行目か(一番下の行 = 1)
    function blankRow(b, n) { return n - Math.floor(b.indexOf(0) / n); }
    // 判定の合計 — 偶数幅は逆転 + 空きマスの行、奇数幅は逆転のみ
    function parity(b, n) { return n % 2 === 0 ? inversions(b) + blankRow(b, n) : inversions(b); }
    function solvable(b, n) {
        return n % 2 === 0 ? parity(b, n) % 2 === 1 : parity(b, n) % 2 === 0;
    }

最初の盤は逆転27・空きマスの行2・合計29(奇数)で解け、1.8秒にタイル5と9を入れ替えると合計が32(偶数)になり、続く8手で34・36・40と動いても偶奇は偶数のままでした。

03元の位置までの距離を色で塗るマンハッタンのヒートマップ

タイルごとに今のマスと元のマスの横と縦のマス数を足したマンハッタン距離を求め、色の濃さで塗るので、どのタイルが元の位置から遠いかがひと目で読めます。色は距離0の薄いミントから3の黄、6以上のバラ色まで heatColor が距離の比で混ぜて決め、盤全体の距離の合計Hも数字で並べて見せます。

元の位置までの距離を色で塗るマンハッタンのヒートマップ
新しいタブで開く

03 · 元の位置までの距離を色で塗るマンハッタンのヒートマップ — 計測 累積面積 18.897% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

manhattanheatsumH
    function manhattan(b, n, i) {
        const v = b[i];
        if (v === 0) {
            return 0;
        }
        const h = v - 1;
        return Math.abs((i % n) - (h % n)) + Math.abs(Math.floor(i / n) - Math.floor(h / n));
    }

四つの盤を測ると、一手ごとのHの変化は±1ずつで、終わりは0になります。種7の盤はH 22から始まって最短26手・ノード700で解け(上がった手2・下がった手24)、種18の盤はH 18・20手・ノード236で最も短くなりました。

04完成した盤から歩いて出る混ぜ方

完成した盤から始めて、空きマスを SHUFFLE_STEPS の60回、隣のマスへ動かす混ぜ方で、規則どおりに歩いて出た盤なので02番の判定は解けると出ます。いま来たマスへ戻る手は飛ばし、どの隣へ行くかは整数のハッシュで選びます。

完成した盤から歩いて出る混ぜ方
新しいタブで開く

04 · 完成した盤から歩いて出る混ぜ方 — 計測 累積面積 27.604% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

SHUFFLE_STEPShashnoBacktrack
    function walkMoves(n, steps, seed) {
        const b = solvedBoard(n);
        const out = [];
        let noBacktrack = -1;
        for (let s = 0; s < steps; s += 1) {
            const opts = [];
            for (let d = 0; d < 4; d += 1) {
                if (d !== noBacktrack && canStep(b, n, d)) {
                    opts.push(d);
                }
            }
            const d = opts[Math.floor(hash2(s, seed) * opts.length)];
            blankStep(b, n, d);
            out.push(d);
            noBacktrack = d ^ 1;
        }
        return out;
    }

同じ種41の60歩を一歩ごとに調べると solvable は60/60で真、最初の10歩はHが一歩に1ずつ1から10まで上がり、60歩でH 30・元の位置にあるタイル0枚になります。比較に置いた上の段のハッシュによる無作為な配置は1,000盤中490盤(49.0%)だけが解けました。

05上限を引き上げながら最短手を探す反復深化探索

マンハッタン距離の合計Hを手がかりに深さ優先で探索し、ここまでの手数とHの合計が上限を超えたら枝を畳んで、上限を一段上げてやり直す方式です。ノード数が NODE_CAP の4000に届いたら止まったと示し、終わったら見つけた手を一手ずつ再生します。

上限を引き上げながら最短手を探す反復深化探索
新しいタブで開く

05 · 上限を引き上げながら最短手を探す反復深化探索 — 計測 累積面積 26.812% · 動いたフレーム 22/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

NODE_CAPboundidaStar
        function dfs(g, h, bound, last) {
            nodes += 1;
            if (nodes > cap) {
                capHit = true;
                return INF;
            }
            const f = g + h;
            if (f > bound) {
                return f;
            }
            if (h === 0) {
                return -1;
            }
            let min = INF;
            for (let d = 0; d < 4; d += 1) {
                if (last >= 0 && d === (last ^ 1)) {
                    continue;
                }

探索済みの盤を溜めずに深さ優先で進むので、最短手を求める流れを学ぶ例にも向きます。3×3の四つの盤の実測はHが10〜18、解は20〜26手、ノードは1,429〜2,800で、上限を上げるたびにノードは階段のように増えました(種2の盤は上限14〜24で3・8・57・313・1,261・1,158個)。

06一枚の絵をタイルに切って継ぎ目が見える盤

キャンバスにノイズで夕空・太陽・丘を一枚描き、TILE_N の4×4のマスに切って drawImage でタイルに写します。最後のマスは空けておき、タイルごとに SEAM_PX の2の暗い縁と上側のハイライトを載せるので、数字の代わりに絵で合わせるパズル画面になります。

一枚の絵をタイルに切って継ぎ目が見える盤
新しいタブで開く

06 · 一枚の絵をタイルに切って継ぎ目が見える盤 — 計測 累積面積 32.667% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

drawImageSEAM_PXtileCut
    function tileCut(v, px, py, wk) {
        const hc = (v - 1) % BN;
        const hr = Math.floor((v - 1) / BN);
        const sz = BSZ / BN;
        const x = BX + px * CS + 1;
        const y = BY + py * CS + 1;
        const s = CS - 2;
        ctx.save();
        ctx.beginPath();
        ctx.roundRect(x, y, s, s, lerp(6, 0, wk));
        ctx.clip();
        ctx.drawImage(picCv, hc * sz, hr * sz, sz, sz, x, y, s, s);
        ctx.restore();

そろえていくと絵が一枚現れ、完成後の0.6秒で継ぎ目が薄くなります。216×216の絵をマス54pxで切ると、タイル15枚・解く手16・完成2.37秒で、切り出しは MDN の drawImage の文書にある元の領域から先の領域へのコピーそのものです。

07ドラッグして離すとマスに吸いつくポインター

タイルを押してドラッグすると、空きマスの向きの一軸にだけ付いてきて、一マスの幅を超えないように切ります。離したとき移動量が SNAP_RATIO の0.5を超えれば空きマスに入り、届かなければ元に戻り、ポインターイベント一つでマウスとタッチが同時に使えます。

ドラッグして離すとマスに吸いつくポインター
新しいタブで開く

07 · ドラッグして離すとマスに吸いつくポインター — 計測 累積面積 12.728% · 動いたフレーム 19/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

SNAP_RATIOpointerclamp
    function dragMove(x, y) {
        if (!dragging) {
            return;
        }
        ptrX = x;
        ptrY = y;
        rawK = ((x - startX) * axX + (y - startY) * axY) / CS;
        const k = clampK();
        dragCx = (dragCell % BN) + axX * k;
        dragCy = Math.floor(dragCell / BN) + axY * k;
    }

ドラッグ幅を変えた八回の実測は吸着5・戻り3で、0.85・0.62・0.7マスは吸いつき、0.3・0.42・0.25マスは戻り、1.45・1.2マスは一マスで切られて1.00になってから吸いつきます。一回のドラッグは0.36秒の移動と0.12秒の保持で、入力は MDN の Pointer events の文書にある統合された入力の仕組みを使います。

08取り消しの記録と解法の再生

押した手をスタックに積み、取り消し一回で一手ずつ取り出します。解法を再生するときは、反対向きの手が隣り合っていたら二つを消して長さを縮め、REPLAY_MS の220ms間隔で一手ずつ見せ、縮めた手数と元の手数は数字で並べて書きます。

取り消しの記録と解法の再生
新しいタブで開く

08 · 取り消しの記録と解法の再生 — 計測 累積面積 14.764% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

REPLAY_MSstackcancelPair
    function cancelPair(ms) {
        const out = [];
        for (let i = 0; i < ms.length; i += 1) {
            if (out.length > 0 && out[out.length - 1] === (ms[i] ^ 1)) {
                out.pop();
            }
            else {
                out.push(ms[i]);
            }
        }
        return out;
    }

間違えた手を戻し、解いた過程をもう一度見せる機能にそのまま使えます。四つの盤で14手のうち3回戻してスタックに11手を残し、縮めた手数は5・7・7・3(消えた組は3・2・2・4)で、最初の盤から縮めた手だけで再生した結果は11手をそのまま積んだ盤とマスごとに同じでした(最初の盤の再生は5手 × 220ms = 1.1秒)。

09盤の大きさごとの状態数と探索ノードの比較

2×2・3×3・4×4の盤で取りうる配置の数を、n×nの階乗を2で割った数として計算し、対数目盛の棒で見せます。同じ混ぜの種で05番の探索を回した結果のノード数を横に置きます。

盤の大きさごとの状態数と探索ノードの比較
新しいタブで開く

09 · 盤の大きさごとの状態数と探索ノードの比較 — 計測 累積面積 12.89% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

TILE_NstateCountlogBar
    function stateCount(n) {
        let f = 1;
        for (let i = 2; i <= n * n; i += 1) {
            f *= i;
        }
        return f / 2;
    }
    // 対数目盛の棒 — 値の常用対数を上限の対数で割った0〜1
    function logBar(v, top) {
        return clamp(Math.log10(Math.max(1, v)) / Math.log10(top), 0, 1);
    }

盤の大きさを決めるときに難しさがどう跳ねるかを見積もる目安です。配置数は2×2が12、3×3が181,440、4×4が約1.05e13で、12から181,440は15,120倍、181,440から1.05e13は約5,770万倍に跳ね、種8ではノード数が2×2で7個(解6手)・3×3で303個(14手)・4×4で3,600個(28手)と、盤が大きいほど探索も重くなります。

スライドパズルをコードで作ると、タイル一枚の動きはどんな値がいくつで決まるのでしょうか。

盤の配列と空きマスの向きが決めます

盤は番号の配列 bd(0が空きマス、タイル v の元の位置は v-1 番のマス)ひとつで、空きマスの向き d は0が右・1が左・2が下・3が上の四つ、反対向きは d ^ 1 です。一手は配列の二つのマスの入れ替えにすぎません。

値 意味 変える場所
bd 盤の状態(0が空きマス) rowChain・blankStep・walkMoves
d 空きマスの移動の向き 方向キー・ドラッグ・探索
H マンハッタン距離の合計 manhattan・sumH(03・05)

一つの盤からいくつもの計算が生まれます

同じ bd に対して、inversions は判定を、manhattan は距離を、walkMoves は混ぜ方を計算します。場面が九つあっても配列を作る規則はひとつなので、別の場面の関数でも同じ配列をそのまま調べられます。

盤を番号の配列で持ち、空きマスの隣のタイルを選んで入れ替え、その結果をマスの座標に移して描く — スライドパズルの一手が処理される順番

配列が先で、画面があとから追います

押したりドラッグしたりすると配列の入れ替えが先に起き、画面のタイルは目標のマスへ SLIDE_MS か SETTLE_S の補間で追いかけます。補間の途中でもう一度押しても盤の状態はすでに決まっているのでずれません。drawImage で絵を写す06も同じ順番です。

上限ごとのノードの階段

05の探索は上限をHから始め、失敗するたびに受け取った最小の超過値へ引き上げます。上限ごとのノード数を perBound に積んで画面に行として見せるので、上限が一段上がるたびに探索がどれだけ膨らむかが数字で読めます。

スライドパズルのゲームのように実際の画面に付けるとき — ライブラリなしの作り方・タッチとマウスの入力・混ぜる時点

ライブラリなしの作り方

キャンバス2Dがあれば足ります。九つの場面はライブラリ・WebGL・CDNを使わず、ソース一つのファイルに計算の関数と場面のデモを一緒に入れました。「スライドパズル 無料」で探す人も、外部のサービスに頼らずこのページの上で動かして確かめられます。

タッチとマウスの入力

07は pointerdown・pointermove・pointerup・pointercancel と setPointerCapture でドラッグを処理し、舞台の箱に touch-action: none を付けるので、ドラッグ中にページが一緒にスクロールしません。ほかの場面は方向キーとタイルの押下で同じ配列の関数を呼びます。

混ぜる時点

盤を見せる前に walkMoves で歩いておけば、解けない盤が出る隙がありません。すでに受け取った盤なら、絵を描く前に solvable で先に判定します。「スライドパズル コツ」を一つだけ挙げるなら、この判定を画面より前に置くことです。

ジグソー編との違い

ジグソーパズルの編 はピースの形と隣のピースとの結合を扱い、この編は空きマスとの入れ替えの規則と解ける盤の判定を扱います。格子の規則を探索で解く流れが気になるなら、迷路の生成の編 も同じ計算の枠組みを使っています。

スライドパズルが壊れる落とし穴 — でたらめに混ぜて解けない盤ができること・探索が深くなりすぎて画面が止まること・ドラッグして離したときタイルがマスの間に残ること

でたらめに混ぜると解けない盤ができます

配列を無作為に並べ替えると、解ける盤は半分ほどです。ハッシュによる無作為な配置1,000盤のうち解けたのは490盤でした。解けない盤を除くには、02の判定を描く前に回すか、04のように規則どおりの手だけで混ぜます。二枚を入れ替えた盤は、その後に何手重ねても偶奇が戻りません。

探索が深くなりすぎると画面が止まります

4×4の盤を上限なしで探索するとノードは数十万を超え、上限を300,000にしても四つの盤のうち三つが終わりませんでした。画面が固まるのを防ぐのが NODE_CAP の4000で、届いたら「上限に到達」と示してやめます。実際のサービスでは上限を大きく取るか、ウェブワーカーで回します。

ドラッグして離すとタイルがマスの間に残ります

ドラッグを一マスの幅で切らないと、タイルが隣のマスの上に重なり、離した瞬間にどのマスへ付けるか曖昧になります。clampK で0〜1マスの中に切り、SNAP_RATIO で吸着か戻りかを一度に決めれば、タイルがマスの間で止まったままになりません。

この記事の九つの場面の全ソースと編集用のファイルは、下の箱のzipで受け取れます。開くための圧縮パスワードは mvvxprjw です。

盤の大きさとスライド時間と混ぜる手数を変えると感じはどれだけ変わるか — TILE_N・SLIDE_MS・SHUFFLE_STEPSを変えた違い

名前 変えた値 感じ
盤をもっと大きく 06 TILE_N 4 → 5 TILE_N を4から5に上げるとタイルが15枚から24枚に増え、一枚が54pxから43.2pxに小さくなって絵がより細かく切られ継ぎ目が増え、下げると大きな断片が数枚になります。手数は同じなので、解く手16と完成2.37秒は変わりません
スライドをもっとゆっくり 01 SLIDE_MS 140 → 400 SLIDE_MS を140から400に伸ばすと三枚が動き終わるまでが200msから460msに延びる一方、STAGGER_MS の30msのずれは変わらないので、順に付いていく様子はひとかたまりにぼやけ、縮めるとずれが目立ちます
混ぜる手数を少なく 04 SHUFFLE_STEPS 60 → 12 SHUFFLE_STEPS を60から12に減らすと距離の合計Hが30から12に下がり(元の位置にあるタイルは0枚から3枚)、解く手が短くなります。種41〜60の二十の盤の平均Hは12歩で10.6・60歩で24.7・300歩で38.4でした

この三つの値は互いに干渉しません。TILE_N はピースの数と大きさだけ、SLIDE_MS は画面の補間だけ、SHUFFLE_STEPS は混ざり具合だけを変えるので、一度にひとつずつ変えて、どの値が感じを変えたのか見るのがよいでしょう。

動きを減らす設定ではタイルがすぐ入れ替わる盤一枚 — 場面名と今そろったタイルの数を文で読み上げるアクセシビリティ

方向キーでタイルを動かし、取り消しはUです

舞台の箱は九つの場面とも role="application" で tabindex 0 なのでフォーカスを受け取り、方向キーはその向きに動くタイルを動かし、Enter・Space・Pは一時停止、Nは一歩、Rは最初からです。08はU・Z・Backspaceで一手戻し、07はタイルをドラッグして離します。

読み上げはモードが変わるときだけです

画面の状態の行は aria-live="off" でデモ中は読まれず、role="status" の隠した段落に speakText() で場面名と今そろったタイルの数を文で書きます。書くのは操作した直後とモードが変わるときだけなので、自動のデモ中に読み上げが流れることはありません。

動きを減らす設定と隠れたタブ

prefers-reduced-motion が有効なときはループを回さず、時間表の停止の時刻の一枚だけを描くので、タイルは補間なしで目標のマスにすぐ収まります。タブが隠れたらループを止め、戻ったら積んだ時間を捨てて続きから動かします。この処理は MDN の prefers-reduced-motion の文書に沿っています。

    // タブが隠れたら止め、戻ったら時計を合わせ直して始める — 隠れていた数秒が一フレームに集まらないように
    document.addEventListener('visibilitychange', function () {
        if (document.hidden) {
            stopLoop();
        }
        else if (!paused && !still) {
            startLoop();
        }
    }, { signal: off.signal });
    // 設定が変わったら — 有効なら停止の場面一枚、無効なら再び動かす
    reduceQuery.addEventListener('change', function () {
        still = reduceQuery.matches;
        if (still) {
            showRest();
        }
        else {
            lap = 0;
            play();
        }
    }, { signal: off.signal });

スライドパズルのFAQ — スライドパズルの解き方・解けない盤ができる理由・ウェブに載せるときに必要なもの

スライドパズルの解き方をコードで手伝えますか

03のマンハッタン距離で元の位置から遠いタイルを選んで動かしていくとHが0に向かって下がり、行き詰まったら05の反復深化探索が最短手を探して一手ずつ見せます。Hは各タイルが元の位置まであと何マスかを足した目安で、0になれば完成です。

解けない盤はなぜできますか

二枚のタイルを入れ替えると逆転の数の偶奇が反転し、解けない側へ移ります。規則どおりの手だけではこの偶奇が変わらないので、無作為に混ぜた盤の半分ほどは解けない盤になり、02は判定の値を実時間で見せます。

ウェブに載せるときは何が必要ですか

静的なファイル一式で足ります。キャンバスは devicePixelRatio を2までしか掛けず、外部のフォントもサーバー呼び出しもないので、どの静的ホスティングにも載せられます。

出典の文書は MDN の requestAnimationFrame の項目です。

解凍パスワードを入力してください

パスワードはこの記事の本文の中にあります。読み進めると出てきます。