GridNine ができるまで — 唯一解の数独をブラウザで生成する

数独（ナンプレ）を作るのは、解くよりずっと難しい——作ってみて初めて分かったことです。

盤面に数字を適当に置いて空きを作れば問題になる、と思っていました。ところが数独には「解が 1 つだけ」という絶対のルールがあります。解が 2 通り以上ある盤面は、論理だけでは解けず、当てずっぽうが必要になる。それは数独ではありません。

GridNine は、必ず唯一解を持つ数独を自動生成するツールです。生成も、正誤判定も、ヒントも、全部ブラウザの中で計算します。この記事は、その「唯一解を保証する」ところの話が中心です。

#🎯 唯一解でなければ数独じゃない

数独の面白さは、「マスを一つひとつ論理で確定できる」ことにあります。空きマスに入る数字が、ルール（同じ行・列・3×3 ブロックに同じ数字は入らない）から一意に決まっていく。この一本道があるから、解いていて気持ちいい。

解が複数あると、この一本道が途中で分岐します。「ここは 3 か 7 か、どちらでも成立する」——こうなると論理では詰められず、勘で選ぶしかない。良い数独パズルは、絶対に唯一解でなければならない。生成の全設計が、この一点のためにあります。

#🏗️ まず「解く力」を作る

生成の前に、解くエンジンが要ります。唯一解かどうかを確かめるには、その盤面を実際に解いてみるしかないからです。

数独ソルバーの核は、候補が最も少ないマスから埋めるバックトラッキングです。

export function solve(grid: number[]): number[] | null {
 const work = [...grid]
 const rec = : boolean => {
 let best = -1
 let bestC: number[] | null = null
 for (let i = 0; i < 81; i++) {
 if (work[i] !== 0) continue
 const c = candidatesAt(work, i) // そのマスに入りうる数字

 if (c.length === 0) return false // 入る数字がない → 行き止まり

 if (!bestC || c.length < bestC.length) {
 best = i
 bestC = c // 候補が少ないマスを優先

 }
 }
 if (best === -1) return true // 空きマスがない → 完成

 for (const d of bestC!) {
 work[best] = d
 if (rec) return true
 work[best] = 0 // ダメなら戻す（バックトラック）

 }
 return false
 }
 return rec ? work : null
}

ポイントは candidatesAt で「そのマスに入りうる数字」を先に絞り、最も候補の少ないマスから試すところです。これは制約伝播（constraint propagation）と呼ばれる定石で、探索の枝を劇的に減らします。候補が 1 つしかないマスがあれば、それは確定なので迷わず埋まる。9 択を総当たりするのに比べ、桁違いに速くなります。

#🔑 唯一解の判定：解を 2 つまで数える

「唯一解か?」を確かめるのに、全部の解を数える必要はありません。2 つ目が見つかった瞬間に、唯一解ではないと分かるからです。

export function countSolutions(grid: number[], limit: number): number {
 let count = 0
 const work = [...grid]
 const rec = => {
 if (count >= limit) return // limit(=2) に達したら打ち切り

 // ... 候補最少マスを探す ...

 if (best === -1) {
 count++ // 完成盤に到達 = 解が 1 つ見つかった

 return
 }
 for (const d of bestC!) {
 work[best] = d
 rec
 work[best] = 0
 if (count >= limit) return
 }
 }
 rec
 return count
}

limit を 2 にして呼べば、解が 2 つ見つかった時点で探索を止められる。全解を数える必要がないので、「唯一解チェック」が現実的な速度で回ります。この関数が、生成の心臓です。

#⛏️ 生成：完成盤から穴を掘る

数独の生成は、空盤に数字を足すのではなく、完成盤から数字を抜くのが定石です。

まず、ソルバーと同じ手法で（候補をシャッフルしながら）ランダムな完成盤を作ります。

function generateFull: number[] {
 // solve と同じ制約伝播 + バックトラック。

 // ただし候補を shuffle して、毎回違う完成盤を作る

 for (const d of shuffle(bestC!)) { ... }
}

そこから、唯一解を保ちながらマスを 0（空き）にしていきます。

export function generate(diff: Difficulty): Puzzle {
 const solution = generateFull
 const puzzle = [...solution]
 const order = shuffle([...Array(81).keys])
 let givens = 81
 const target = TARGET_GIVENS[diff]
 for (const idx of order) {
 if (givens <= target) break
 const backup = puzzle[idx]
 puzzle[idx] = 0
 if (countSolutions(puzzle, 2) !== 1) {
 puzzle[idx] = backup // 一意でなくなる → 戻す

 } else {
 givens--
 }
 }
 return { puzzle, solution, givens: puzzle.map((v) => v !== 0) }
}

1 マス消すたびに countSolutions(puzzle, 2) を呼び、解が 1 つのままなら消したままに、2 つ以上になったら戻す。これを繰り返すことで、「これ以上消すと唯一解が崩れる」ギリギリまで数字を減らせます。難易度は、残す数字（givens）の目標数で調整します。

穴を掘るたびに唯一解チェックが走るので、生成には解く処理が何十回も呼ばれる——ソルバーの速さが、そのまま生成の速さになります。

#😓 苦労したところ

#難易度は「残す数字の数」だけでは決まらない

givens を減らせば難しくなる、と単純には言えません。同じ 30 マスでも、必要な解法テクニックによって体感難易度は大きく変わります。「候補が 1 つに確定するマスを追うだけ」で解ける盤面もあれば、複数マスの相互関係を読む必要がある盤面もある。

GridNine は givens の数を主軸にしつつ、あくまで「目安の難易度」としています。厳密な難易度分類（要求される解法テクニックによる分類）は、それ自体が一つの研究テーマで、そこまでは踏み込んでいません。正直に「難易度は目安」としているのはこのためです。

#生成が止まらないケースを避ける

穴掘りは「消せるだけ消す」ので、極端に少ない givens を狙うと、唯一解を保てずに戻す処理が延々と続きかねません。目標 givens を現実的な範囲に設定し、order をシャッフルして探索順を散らすことで、妥当な時間で生成が終わるようにしています。

#リアルタイムの重複チェック

解くだけでなく、プレイ中に「今このマスがルール違反か」を即座に示す必要があります。これは生成・求解とは別の軽い処理で、行・列・ブロックの重複を集合で持ち、入力のたびに違反マスをハイライトします。作る・解く・遊ぶで、必要な計算がそれぞれ違うのが面白いところでした。

#🔭 今後の拡張

• 解法テクニックによる難易度分類 — 「naked single だけ」「X-Wing が必要」等で難易度を厳密化
• 対称な盤面 — givens を点対称に配置した、見た目の美しいパズル
• ヒントの段階化 — 答えを出す前に「次に確定できるマス」だけを示す
• 手筋の解説 — なぜそのマスが確定するかを説明する

#💡 このサービスから言えること

「作る」ために「解く」が要る、という入れ子構造。 数独生成の核心は、生成アルゴリズムそのものより、唯一解を判定するソルバーでした。良い問題を作るには、その問題を解ける力が先に要る。これはパズルに限らず、テスト問題でも、ゲームのレベルデザインでも通じる構造だと思います。

技術的には、制約伝播で探索を絞るという一手が効きました。9 マス総当たりでは生成が現実的な速度に乗りませんが、「候補が最少のマスから」に変えるだけで桁違いに速くなる。そして「解を 2 つまで数えて打ち切る」ように、目的に必要な最小限しか計算しない設計が、重い処理を軽く見せます。全解を数える必要はどこにもなかった、というのが一番の学びでした。