数独をプログラムで解くアルゴリズム｜バックトラッキングと候補法

最終更新日：2026/08/26

数独ソルバーは「全部試す探索」と「人間と同じ候補消去」の2系統に分かれます。まず誰でも書けるバックトラッキングで完成させ、次に高速化の定石MRV、最後に唯一解の判定まで、numpredo の公開ソルバーと同じ考え方で順に解説します。

まず知っておくべき2つのアプローチ

数独をプログラムで解く方法は、大きく「探索ベース」と「論理ベース（候補法）」の2つに分かれます。どちらか一方だけで解けるわけではなく、実際のソルバーは両方を使い分けます。

当サイトの数独ソルバーは、候補法で「解き方の手順」を出し、候補法で進めない局面は探索で解の有無を判定しています。まずは探索から理解すると、全体像がつかみやすくなります。

まず完成させる：バックトラッキングの基本形

バックトラッキングは「空きマスに数字を仮に入れ、矛盾したら戻る」深さ優先探索です。ルールさえ実装すれば、どんな問題でも必ず解ける（解がある場合）ため、最初の一歩に最適です。

function solve(grid) {
  const i = emptyCell(grid);    // 空きマスを1つ選ぶ
  if (i === -1) return grid;    // 全部埋まったら完成
  for (let n = 1; n <= 9; n++) {
    if (canPlace(grid, i, n)) { // 行・列・ブロックの重複チェック
      grid[i] = n;
      const result = solve(grid);
      if (result) return result; // 解けたらそのまま返す
      grid[i] = 0;               // 失敗したら戻す（バックトラック）
    }
  }
  return null;                   // この分岐では解なし
}

ポイントは canPlace（同じ行・列・3×3ブロックに n が既に無いか）と、失敗したときに grid[i] = 0 で戻すことの2つだけです。最初の空きマスから順に試しても、初級〜中級なら十分実用的な速度で解けます。

高速化の定石：MRV（最小残り値）

バックトラッキングの速度は「どのマスから試すか」で大きく変わります。候補が1つしかないマスを後回しにすると、無駄な仮置きを繰り返します。MRV（Minimum Remaining Values）は「候補が最も少ないマスから試す」というヒューリスティックです。

// 候補が最も少ない空きマスを選ぶ（MRV）
function nextCell(grid) {
  let best = -1, bestCount = 10;
  for (let i = 0; i < 81; i++) {
    if (grid[i] !== 0) continue;
    const c = countCandidates(grid, i);
    if (c < bestCount) { bestCount = c; best = i; }
    if (bestCount === 1) break; // これ以上少なくならない
  }
  return best;
}

空きマスを順番に選ぶ代わりに nextCell() を使うだけで、探索回数が数桁減ることがあります。さらに「候補の少ない数字から試す」ことや、確定した数字で周囲の候補を更新する（制約伝播）を足すと、一般的な9×9ならほぼ一瞬で解けます。

候補法（制約伝播）で「根拠つきの手順」を出す

探索は答えを出しますが、「なぜその数字が入るのか」は教えてくれません。人間向けの解説や次の一手の提示には、候補法を使います。まず全空きマスの候補（そのマスに入りうる数字の集合）を計算し、確定した数字で周囲の候補を消していくのが基本です。

当サイトの候補数字・次の一手チェッカーは、この候補計算を毎回行い、「同じ行・列・ブロックに5があるから候補から消える」といった理由を1数字ずつ表示します。numpredo のエンジンでは候補をビットマスク（1〜9を9ビットで表現）で持ち、単数・ペア・X-Wingなどの手筋を順番に適用して解き方の手順を生成しています。

// 候補は「そのマスに入りうる数字」の集合
candidates[i] = {1,2,3,4,5,6,7,8,9}
              - {同じ行にある数字}
              - {同じ列にある数字}
              - {同じブロックにある数字}

// 候補が1つになったマスは確定（裸の単数）
if (candidates[i] の要素数 === 1) {
  grid[i] = その数字;
  同じ行・列・ブロックの候補から消す;
}

唯一解の判定：解を2つ見つけたら止める

数独は「解が一つだけ」であることが品質の条件です。解の数を数えるとき、全部を数え続けると指数関数的に遅くなるため、2つ見つけた時点で打ち切るのが定石です。「0個＝解なし」「1個＝唯一解」「2個以上＝複数解」で判定できます。

let count = 0;
function countSolutions(grid) {
  const i = emptyCell(grid);
  if (i === -1) { count++; return; }
  for (let n = 1; n <= 9; n++) {
    if (!canPlace(grid, i, n)) continue;
    grid[i] = n;
    countSolutions(grid);
    if (count >= 2) { grid[i] = 0; return; } // 2つ目で即終了
    grid[i] = 0;
  }
}

numpredo のエンジンも同じ方針で、countSolutions(grid, 2) という形で「数える上限2」を渡しています。全掲載問題はこの判定と、論理手順だけで完答できることの両方をパスしています。詳しい集計は全4,395問の分析データで公開中です。

手を動かして確かめる（無料・ブラウザで実行）

ここまでの考え方を、実際のツールで確かめられます。数独ソルバーに盤面を入力すると、候補法で進められる範囲は手筋つきの手順が、解の有無と唯一解は探索で判定されます。候補数字チェッカーなら、任意のマスの候補と「なぜ消えるか」を1数字ずつ確認できます。

自分の実装と比べる際は、まず初級の問題（無料プレイ）をテキスト形式で貼り付けられる形にすると比較しやすいでしょう。ルールの定義は数独のルール・遊び方を参照してください。

さらに先へ：16×16・キラー・DLX

9×9を解けるようになったら、拡張にも挑戦できます。16×16ナンプレは4×4ブロック版で、探索は同じ考え方で通用します（数字が1〜9・A〜Gの16種類になるだけ）。キラー数独は「合計の制約」が加わるため、候補法に足し算の組み合わせ判定が必要になります。

より高度な話題として、Donald Knuth が考案した Dancing Links（DLX）という「解ける問題を厳密に解く」方式もあります。まずはバックトラッキングと候補法で十分速いので、興味があれば調べてみてください。

解き方ガイドに戻る

• 解き方完全ガイド
• 上級をプレイして練習

よくある質問

数独ソルバーは何語で書くのがいいですか？

最初はPythonやJavaScriptなど書き慣れた言語で十分です。バックトラッキングと候補法はどの言語でも同じ構造で書けます。処理速度を極めたい場合はCやRustを検討してもよいですが、9×9なら一般的な言語で十分実用的です。

バックトラッキングの計算量はどのくらいですか？

素朴な実装では空きマスごとに最大9通りの仮置きを試すため、最悪ケースで非常に大きくなります。MRV（候補が少ないマスから試す）と候補の制約伝播を入れると、通常の9×9問題はほぼ一瞬で解けます。

数独に複数の解があるかどうかはどう判定しますか？

解を2つ見つけた時点で探索を打ち切るのが定石です。「0個＝解なし」「1個＝唯一解」「2個以上＝複数解」と判定します。全部数えると指数関数的に遅くなるため、上限2で止めるのがポイントです。

新聞や本の数独をプログラムで解いてもいいですか？

個人で解く・検算するためのプログラム利用は一般的です。ただし、解いた問題の再配布や商用利用は元の出版物の利用条件に従ってください。手元の問題をすぐ答え合わせしたい場合は無料ソルバーが使えます。

人間向けの「解き方の手順」もプログラムで出せますか？

出せます。候補法（制約伝播）で単数やペアなどの手筋を順番に適用し、その履歴を記録すれば「どのマスが、どの手筋で確定したか」を手順として表示できます。当サイトのソルバーもこの方式で一手ずつの解説を表示します。

16×16やキラー数独も同じアルゴリズムで解けますか？

16×16は数字が16種類になるだけで同じ考え方で解けます。キラー数独は「ケージの合計」という追加制約があるため、候補の計算に足し算の組み合わせ判定を加える必要があります。当サイトでは16×16ソルバーとキラー数独を公開しています。