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

数独 9種 — 候補の絞り込みから解がひとつの盤づくりまで

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

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

数独は当てずっぽうで解くゲームではありません。01番はマスごとの候補をビットひとつずつ消し、03番は候補がいちばん少ないマスから戻りながら解き、04番は穴を開けるたびに解がひとつだけか数えます。

数独は空きマスに数字を当ててみるゲームではなく、行・列・3×3の箱ですでに出た数字を消して、残った候補から解く計算です — 数独のゲームを作るには、候補をどんな値で持つかを決めることから始まります

マスごとの候補をビットで消す絞り込み図01 sd-candidate-bitmask-map ひとつだけの候補を埋めると次が解ける連鎖02 sd-single-fill-cascade 候補がいちばん少ないマスから戻る探索03 sd-fewest-first-backtrack 穴を開けるたびに解の数を数える盤づくり04 sd-unique-dig-count 同じ行・箱で重なった数字を示す衝突の表示05 sd-conflict-peer-mark 理由まで見せるヒント — どの行が候補を消したか06 sd-hint-reason-trace 数字ごとの残り数をリングで縮めるキーパッド07 sd-digit-left-ring 完成するとマスごとに時間差で広がる波08 sd-solved-wave-flourish 必要な手筋で測る難易度の点数バー09 sd-difficulty-score-bar

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

数独 解き方の基本は消去なので、九つの場面は同じ盤のモデルをひとつ使い、場面ごとに違うのはその盤から読む値だけです。候補をマスごとに別々に書き留めず盤の配列からそのつど計算すると、数字が変わった瞬間に候補も一緒に変わります。

候補は9ビットの整数ひとつです

盤は81マスの数字の配列(0は空きマス)で、数字dは(d-1)番目のビットで表します。全部の候補は ALL の511なので候補の集合がそのまま整数ひとつになり、残った候補の数は立っているビットを数える popcount で分かります。

乱数なしで同じ盤がもう一度出ます

盤は整数のハッシュ hash2(a, b) で混ぜた完成盤から穴を開けて作ります。同じ種なら同じ盤が出て、時間は場面の時計ひとつを1/60秒の固定の歩幅で消化します。

    const ALL = 511;
    function bit(d) { return 1 << (d - 1); }
    function popcount(m) {
        let c = 0;
        let v = m;
        while (v) {
            v &= v - 1;
            c += 1;
        }
        return c;
    }

数独 9種 — 候補の絞り込み図・ひとつだけの候補の連鎖埋め・候補の少ないマスから戻る探索・解がひとつの盤づくり・重なった数字の表示・理由を見せるヒント・数字ごとの残り数・完成の波・難易度の点数

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

場面 累積面積 動いたフレーム 強さの平均
01 候補の絞り込み図 21.3% 23/23 46.1
02 連鎖埋め 24.6% 23/23 40.3
03 少ないマスから戻る探索 12.4% 21/23 96.7
04 穴を開ける盤づくり 20.9% 21/23 29.7
05 重なりの表示 17.1% 14/23 42.8
06 絞り込みの根拠ヒント 8.2% 9/23 58.9
07 残り数のリング 20.8% 18/23 53.9
08 完成の波 31.9% 17/23 92.5
09 難易度の点数 20.4% 21/23 123.8

累積面積が最も広いのは08の31.9%で、最も狭いのは06の8.2%です。動いたフレームは01と02が23/23、06が9/23でいちばん少なく、強さの平均は09の123.8が最高、04の29.7が最低です。

01マスごとの候補をビットで消す絞り込み図

マスごとに1〜9を9ビットひとつで持ち、同じ行・列・箱にある数字のビットをORで集めて引くので、メモの候補を自動で入れて消すことに使えます。マスの色は候補がひとつなら緑、七つ以上なら地の色です。ノードで関数をそのまま動かすと、盤の空きマスの候補と一致します。

マスごとの候補をビットで消す絞り込み図
新しいタブで開く

01 · マスごとの候補をビットで消す絞り込み図 — 計測 累積面積 21.349% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

candMaskPEERSpopcount
    // マスiが属するkindの組からiを除いたマスがすでに使った数字のビットの合計(OR)
    function usedMask(b, i, kind) {
        const u = UNITS[unitIndex(kind, i)];
        let m = 0;
        for (let k = 0; k < 9; k += 1) {
            if (u[k] !== i && b[u[k]] !== 0) {
                m |= bit(b[u[k]]);
            }
        }
        return m;
    }
    // 候補 = 9ビット全体から三つの組が使ったビットを引いたもの。埋まったマスの候補は0
    function candMask(b, i) {
        if (b[i] !== 0) {
            return 0;
        }
        return ALL & ~(usedMask(b, i, 0) | usedMask(b, i, 1) | usedMask(b, i, 2));
    }

ノードで動かすと、四つの盤の空きマス188マスすべてでこのビット計算が集合で数えた候補と一致し、最初の盤は場面が置く8マスを埋めると空きマスが47から39に、1マスあたりの平均の候補が3.15から2.28に減ります。

02ひとつだけの候補を埋めると次が解ける連鎖

候補がちょうどひとつのマスを埋めて候補を数え直すことを繰り返すので、人が詰まったときに次のマスを示す画面に使えます。

ひとつだけの候補を埋めると次が解ける連鎖
新しいタブで開く

02 · ひとつだけの候補を埋めると次が解ける連鎖 — 計測 累積面積 24.627% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

singlesFillorderisStuck
    function singlesFill(start) {
        const b = start.slice();
        const order = [];
        const digits = [];
        const avail = [];
        for (;;) {
            let first = -1;
            let n = 0;
            for (let i = 0; i < 81; i += 1) {
                if (b[i] === 0 && popcount(candMask(b, i)) === 1) {
                    if (first < 0) {
                        first = i;
                    }
                    n += 1;
                }
            }
            if (first < 0) {
                break;
            }
            const d = lowDigit(candMask(b, first));
            b[first] = d;
            order.push(first);
            digits.push(d);
            avail.push(n);
        }

ヒント32の四つの盤で埋まったマスは27・20・19・17個で、どれも正解と同じでした。ただし四つとも、ひとつだけの候補では最後まで解けずに止まり、候補がいちばん少ないマスに赤い枠が残ります。

03候補がいちばん少ないマスから戻る探索

ひとつだけの候補で解けなくなったら、候補がいちばん少ないマスに数字を仮置きし、行き詰まれば戻すので、筋が見えない難しい盤を最後まで解くのに使います。仮置きの数は NODE_CAP の400で打ち切ります。

候補がいちばん少ないマスから戻る探索
新しいタブで開く

03 · 候補がいちばん少ないマスから戻る探索 — 計測 累積面積 12.417% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

NODE_CAPsearchdead
            let mm = bm;
            while (mm) {
                const lo = mm & -mm;
                mm ^= lo;
                const d = 32 - Math.clz32(lo);
                r.nodes += 1;
                if (r.nodes > cap) {
                    r.capHit = true;
                    return;
                }
                b[best] = d;
                rm[rowOf(best)] |= lo;
                cm[colOf(best)] |= lo;
                xm[boxOf(best)] |= lo;
                if (wantTrace) {
                    r.trace.push((best << 4) | d);
                }
                rec();

ヒント24〜25の四つの盤は、候補の少ないマスから解くとノード150・167・173・244個で解け、最初の空き順で解くと四つとも上限の20,000に届いて20,001ノードで止まります。

04穴を開けるたびに解の数を数える盤づくり

完成した盤からマスをひとつずつ空にして解の数を2までだけ数え、ひとつなら空きのまま、二つ以上なら数字を戻すので、解がひとつだけの新しい盤を出し続けるときに使います。

穴を開けるたびに解の数を数える盤づくり
新しいタブで開く

04 · 穴を開けるたびに解の数を数える盤づくり — 計測 累積面積 20.873% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

CLUESdigBoardsearch
    function digBoard(sol, seed, target, singlesOnly) {
        const puz = sol.slice();
        const order = perm(81, seed * 31 + 5);
        const steps = [];
        let clues = 81;
        for (let k = 0; k < 81; k += 1) {
            if (clues <= target) {
                break;
            }
            const c = order[k];
            const d = puz[c];
            puz[c] = 0;
            const s = search(puz, 2, 6000, false, false);
            const cnt = s.capHit ? 2 : Math.min(2, s.count);
            const ok = cnt === 1 && (!singlesOnly || singlesFill(puz).solved);
            steps.push({ cell: c, cnt: cnt, ok: ok, nodes: s.nodes });
            if (ok) {
                clues -= 1;
            }
            else {
                puz[c] = d;
            }
        }
        return { puz: puz, steps: steps, clues: clues };
    }

CLUES を36にして四つの盤を作ると、試した回数は47・46・45・45回、戻したマスは2・1・0・0個で、四つとも最終のヒントは36、解の数は1でした。

05同じ行・列・箱で重なった数字を示す衝突の表示

置いた数字が同じ行・列・箱にすでにあると、重なった二つのマスをバラ色に塗って間違った入力をすぐ示します。表示するのは規則違反だけで、解けない盤かどうかは03番の探索が別に判定します。

同じ行・箱で重なった数字を示す衝突の表示
新しいタブで開く

05 · 同じ行・箱で重なった数字を示す衝突の表示 — 計測 累積面積 17.101% · 動いたフレーム 14/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

conflictssharedKindtintUnit
    // 置いた数字が重なる組 — [マス, マス, 組の種類]
    function conflicts(b) {
        const out = [];
        for (let i = 0; i < 81; i += 1) {
            if (b[i] === 0) {
                continue;
            }
            for (let k = 0; k < 20; k += 1) {
                const p = PEERS[i][k];
                if (p > i && b[p] === b[i]) {
                    out.push([i, p, sharedKind(i, p)]);
                }
            }
        }
        return out;
    }

盤ごとに入力8回のうち規則違反は4回で、間違った入力は0.42秒後に消えます。

06理由まで見せるヒント — どの行が候補を消したか

ヒントが答えの数字だけを知らせず、そのマスの候補を消した行・列・箱を順に光らせるので、なぜその数字なのかを学ばせる画面に使います。

理由まで見せるヒント — どの行が候補を消したか
新しいタブで開く

06 · 理由まで見せるヒント — どの行が候補を消したか — 計測 累積面積 8.234% · 動いたフレーム 9/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

computeHintwhysleftMask
    function computeHint(c) {
        hintCell = c;
        whys = [];
        if (g[c] !== 0) {
            leftMask = 0;
            hintCell = -1;
            return;
        }
        const cand = candMask(g, c);
        leftMask = cand;
        let n = 0;
        for (let d = 1; d <= 9; d += 1) {
            if ((cand & bit(d)) !== 0) {
                continue;
            }
            const srcs = [-1, -1, -1];
            for (let kind = 0; kind < 3; kind += 1) {
                const u = UNITS[unitIndex(kind, c)];
                for (let k = 0; k < 9; k += 1) {
                    if (u[k] !== c && g[u[k]] === d) {
                        srcs[kind] = u[k];
                    }
                }
            }
            let pick = -1;

四つの盤の目的のマスは59・41・20・48番で、候補から外れた数字の根拠はマスごとに8個、行・列・箱の三種類がすべて出ます。最後にビットがひとつ残り、その数字がマスに現れます。

07数字ごとの残り数をリングで縮めるキーパッド

1〜9の各キーにまだ置いていない数を輪の弧で描き、9個置くとキーが薄くなるので、どの数字があと何個かひと目で分かる入力パネルになります。

数字ごとの残り数をリングで縮めるキーパッド
新しいタブで開く

07 · 数字ごとの残り数をリングで縮めるキーパッド — 計測 累積面積 20.815% · 動いたフレーム 18/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

leftOfselDigitARC_RATE
    function leftOf(d) {
        let c = 0;
        for (let i = 0; i < 81; i += 1) {
            if (g[i] === d) {
                c += 1;
            }
        }
        return 9 - c;
    }

弧は一気に縮まず ARC_RATE の9で目標の長さを追い、最初の盤の残り数は[1,4,2,5,4,7,5,5,4]で合計37です。場面は残りがいちばん少ない三つの数字の空きを埋め、三つの盤で7・9・7マスを置きます。

08完成するとマスごとに時間差で広がる波

盤が埋まって重なりがなければ、最後のマスからマンハッタン距離が遠いマスほど遅く明るくなる波が広がり、解けたときのごほうびを出す仕上げの画面になります。時間差は WAVE_MS に距離を掛けた値です。

完成するとマスごとに時間差で広がる波
新しいタブで開く

08 · 完成するとマスごとに時間差で広がる波 — 計測 累積面積 31.885% · 動いたフレーム 17/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

WAVE_MSdistOfwaveP
    function waveP(i) {
        if (solvedT < 0) {
            return -1;
        }
        return (sceneT - solvedT - distOf(i) * WAVE_MS / 1000) / PULSE_S;
    }

三つの盤で最後のマスからいちばん遠いマスの距離は12・12・11で、WAVE_MS が40ならその遅れは480・480・440msで、波ひとつの0.55秒を足すと約1.03秒で終わります。

09必要な手筋で測る難易度の点数バー

ひとつだけの候補で解ければやさしい、仮置きが要れば普通、行き止まりが3回を超えれば難しいと点数を付け、盤ごとに難易度の名前を決めるのに使います。

必要な手筋で測る難易度の点数バー
新しいタブで開く

09 · 必要な手筋で測る難易度の点数バー — 計測 累積面積 20.439% · 動いたフレーム 21/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

rateOfbranchclueScore
    // 点数 — ひとつだけの候補で解ければ0〜39、仮置きが要れば40〜59、戻る探索の行き止まりが3回を超えれば60以上
    function rateOf(puz, solution) {
        const chain = singlesFill(puz);
        const clues = filledOf(puz);
        let score = 0;
        let dead = 0;
        let branch = 0;
        if (chain.solved) {
            score = Math.min(39, 8 + Math.floor((81 - clues) / 1.6));
        }
        else {
            const s = search(puz, 1, 3000, false, false);
            dead = s.dead;
            branch = s.branch;
            score = dead <= 2 ? 40 + Math.min(19, branch * 2 + dead * 4) : 60 + Math.min(39, dead);
        }
        // ヒントの数だけで見た点数 — ヒントが少ないほど難しいと付ける
        const clueScore = clamp(Math.round((46 - clues) * 5), 0, 99);
        return { puz: puz, sol: solution, clues: clues, chain: chain, level: levelOf(score), score: score, clueScore: clueScore, clueLevel: levelOf(clueScore), dead: dead, branch: branch };
    }

ヒント28・40・32・24の四つの盤で、手筋の点数は39・33・46・85、ヒントの数だけで付けた点数は90・30・70・99です。盤1と盤3はヒントの数では難しいのに手筋ではやさしい・普通なので、二つの判定が食い違います。

数独のルールをコードにすると、マスひとつの候補はどんな値がいくつで決まるのでしょうか。

盤の配列と27個の組がすべてです

マスひとつの候補は、そのマスが属する行・列・箱の三つの組が使った数字のビットの合計で決まります。組は行9・列9・箱9の27個で、ひとつのマスの隣は同じ組の別のマス20個です。

値 意味 変える場所
g 盤の状態(0は空きマス) putDigit
PEERS[i] マスiの隣の20マス 絞り込み・重なりの検査
candMask マスの候補のビット 01・02・03・06

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

数独 ルールを一度コードにすれば、同じ盤の配列を使って、singlesFill は連鎖を、search は戻る探索を、conflicts は重なりを計算します。場面が九つあっても候補を作る規則はひとつなので、どの場面の盤でも別の場面の関数で検査できます。

盤を81個の数字の配列で持ち、行・列・箱で使った数字を集めて候補を消し、ひとつだけ残ったマスを埋めてまた消す — 数独が解けていく順番

配列が先で、画面はあとからついてきます

数字が入ると盤の配列が先に変わり、候補と重なりはその配列から計算し直されます。画面の色や棒は計算された値を読んで描くだけなので、補間の途中でまた入力しても盤の状態はずれません。

詰まったら仮置きします

ひとつだけの候補が尽きたら、候補がいちばん少ないマスに数字を置いて進み、候補が0のマスが出たら一段戻します。仮置きの数は nodes、行き止まりは dead で数えるので、場面ごとにどれだけ難しい盤だったかが数字で読めます。

数独のサイトのように実際の画面に付けるとき — ライブラリなしの作り方・タッチとキーボードの入力・盤を作る時点

ライブラリなしの作り方

九つの場面はライブラリ・WebGL・CDNを使わず、ソースの一ファイルに計算の関数と自動デモを一緒に入れています。

タッチとキーボードの入力

ステージの箱は role="application" で tabindex が0なのでフォーカスを受け、矢印キーでマスを移り、1〜9が数字、Delete・Backspace・0が消去、Hがヒントです。ポインターは pointerdown・pointermove・pointerup・pointercancel と setPointerCapture で受け、ステージに touch-action: none を付けて押している間にページが一緒にスクロールしないようにします。

盤を作る時点

数独パズルとして出すなら、利用者が盤を受け取る前に、04番の方法で穴を開けて解の数が1か確かめておくほうが安全です。盤づくりが重いなら上限を置くか、ウェブワーカーに移します。

地雷探しやスライドパズルの編との違い

スライドパズルの編は解ける盤を選り分ける偶奇の判定と街区距離の探索を扱い、この編はマスごとに候補の集合を消して解がひとつか数えることを扱います。格子の上で隣のマスへ広がる計算が気になるなら、地雷探しの編も同じ枠組みを使っています。

数独が壊れる落とし穴 — 解が二つ以上ある盤ができること・戻る探索が深くなりすぎて画面が止まること・メモの候補が入力のあとも古いまま残ること

解が二つ以上ある盤ができます

穴をどのマスにでも開けると解が二つ以上ある盤になり、どの数字が正解か決められません。04番は穴ごとに解の数を2まで数えて二つ以上なら戻すので、四つの盤とも CLUES が36でも26でも解の数は1で終わりました。

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

最初の空き順で解く方法はヒント24〜25の四つの盤すべてで20,000ノードの上限に届きましたが、候補の少ないマスから解くと150〜244ノードで解けました。それでも難しい盤が来ることがあるので、03番の NODE_CAP の400のような上限を置き、届いたら解が見つからなかったと表示して打ち切ります。

メモの候補が入力のあとも古いまま残ります

メモの候補を別に保存すると、数字を置いたあとも消えた候補が残ります。01番のように候補を盤の配列から candMask でそのつど計算すれば、同じ行・列・箱の候補は入力の直後に一致します。

九つの場面のソース一式は下の箱のzipで受け取れ、圧縮を開くパスワードは 6r5snyxx です。

ヒントの数と探索の上限と完成の波の速さを変えると感じはどれだけ変わるか — CLUES・NODE_CAP・WAVE_MSを変えた違い

名前 変えた値 感じ
ヒントをもっと少なく 04 CLUES 36 → 26 CLUESを36から26に減らすと、種4の盤では空きマスが45から55に増え、ひとつだけの候補で埋まるマスが45から4に減って、探索のノードが45から653に増えます。ヒントを増やすと盤がやさしくなります
探索の上限を低く 03 NODE_CAP 400 → 60 NODE_CAPを400から60に下げると、四つの盤すべて(必要なノードは150・167・173・244)が上限に届いて解を見つけられず止まり、400のままであれば四つとも解が見つかります(ソースの関数を動かして数えた値)
完成の波をゆっくり 08 WAVE_MS 40 → 120 WAVE_MSを40から120に伸ばすと、最後のマスからいちばん遠いマス(距離12)の遅れが480msから1,440msに開いて波がゆっくり広がり、縮めるとマスの遅れの間隔が狭まってほとんど一度に点きます

三つの値は別々の段階に掛かっています。CLUES は盤の難しさ、NODE_CAP は探索が止まる地点、WAVE_MS は完成後の画面だけを変えるので、ひとつずつ変えてどの値が感じを変えたか見るのがよいでしょう。ここに挙げたヒント・ノードの数は盤の計算で出した値で、描画を測った値ではありません。

動きを減らす設定では数字がすぐ埋まる盤一枚 — 場面名と埋まったマスの数を文で読み上げるアクセシビリティ

矢印キーと数字キーで自分でも解けます

ステージに触れると時間表が止まり、計算だけが続きます。Nは新しい盤、Rは最初から、Enter・Space・Pは一時停止です。

読み上げは触った直後とモードが変わるときだけです

画面の状態の行は aria-live="off" なので自動デモの間は読まれず、role="status" の隠した段落に場面名と埋まったマスの数を文で書きますが、触った直後とモードが変わるときだけです。自動デモの最中は読み上げが流れません。

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

prefers-reduced-motion がオンなら、ループなしで時間表の停止の時刻までを一度に進めた盤一枚だけを描き、数字が現れる補間と波の模様は描きません。タブが隠れるとループを止め、戻ったらたまった時間を捨てて続けます。設定の名前と動きは 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 — 数独の上級向けの考え方・解がひとつだけの盤の条件・ウェブに載せるときに必要なもの

数独の上級向けの考え方は、コードでどう始めますか

02番のひとつだけの候補を埋める方法がいちばんの基本で、それだけで詰まったら03番のように候補がいちばん少ないマスを選んで仮置きするのが、この編が扱うもう一歩です。06番の絞り込みの根拠を一緒に見れば、どの行が候補を消したか読めます。

解がひとつだけの盤の条件は何ですか

穴を開けて解の数を数えた値がちょうど1であることです。04番は2までだけ数え、二つ以上なら戻してこの条件を守ります。

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

サーバーなしでHTMLファイルひと組を置くだけで動きます。画面の倍率は devicePixelRatio の値を最大2までで使って切り、外部のフォントやサーバー呼び出しもないので、ファイルを置く場所さえあれば足ります。

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

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

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