数独パズルを解くプログラム、というと難しそうに聞こえるかもしれませんが、実はいくつかの基本的な考え方を組み合わせることで、意外とシンプルに実現できるものです。今回は、手元にあるPythonコードを元に、数独ソルバーのアルゴリズムについて、ごく簡単な解説を試みたいと思います。
このコードは、主に以下の3つの要素を組み合わせて、数独を解く仕組みになっています。
バックトラッキング: これは、問題を解くための基本的なアプローチです。空のマスに数字を一つずつ仮に置いてみて、もし途中でルール違反（同じ数字が重複するなど）に行き当たってしまったら、一つ前の状態に戻ってやり直す、という方法です。まるで、迷路の道を一つずつ試していくようなイメージです。
ビットマスク: 少し専門的になりますが、これは効率を上げるための小さな工夫です。数独では、行・列・3x3のブロック内で数字が重複しないようにする必要があります。このチェックを、1〜9の数字を「ビット」という形で管理することで、非常に高速に行うことができます。この方法だと、一つ一つの数字をループで確認するよりも、コンピュータにとってはるかに素早く処理できるのです。
MRVヒューリスティック: 「ヒューリスティック」というのは、絶対的な正解ではないけれど、経験的にうまくいく「発見的な手法」という意味です。このコードでは、次に埋めるマスを選ぶ際に、「候補となる数字が最も少ないマス」 を優先して探します。これは、より早く行き詰まりを発見し、無駄な試行錯誤を減らすための、ちょっとした賢い戦略と言えるかもしれません。
🧩 コードの仕組みについて
具体的に、プログラムはどのように動いているのでしょうか？
まず、Sudoku クラスの初期化（init）では、入力された数独盤面をコピーし、同時に各行・各列・各ブロックで、すでにどの数字が使われているかをビットマスクで記録します。
その上で、solve() メソッドが数独を解く中心的な役割を担います。
まず、まだ数字が入っていないマスの中から、先ほどご説明したMRVヒューリスティックに基づいて、次に試すべきマスを探します。
もし空のマスがなければ、これで数独は完成したということになります。
もし空のマスが見つかったら、そこに置ける候補の数字を一つずつ試していきます。
候補を一つ仮に置いてみて、solve() メソッドをもう一度呼び出します。これは、あたかも「この数字を置いたら、あとは解けるかな？」と試しているようなものです。
もし再帰呼び出しが成功（True を返す）したら、そのまま成功とします。
もしうまくいかなかった場合は、先ほど仮に置いた数字を消して、次の候補を試します。
このようにして、一つずつ可能性を試しながら、解を探索していくわけです。
💡 終わりに
この数独ソルバーは、バックトラッキングという古典的なアルゴリズムと、ビットマスクのような計算機科学的な工夫、そしてMRVヒューリスティックといった探索の効率化手法が組み合わさってできています。
もしご興味があれば、ぜひご自身のパソコンでこのコードを動かしてみてはいかがでしょうか。シンプルなパズルを解くプログラムですが、その裏には意外と奥深いアルゴリズムが隠されているのを感じていただけるかもしれません。
from __future__ import annotations
from typing import List, Optional, Tuple
# 1〜9のビットを立てたマスク (2進数で1111111110 = 0b1111111110)
# → 候補の「全集合」として利用
FULL_MASK = (1 << 10) - 2
N = 9 # 盤面サイズ（数独は9x9固定）
class Sudoku:
"""
数独ソルバクラス。
- 入力: 9x9 の二次元リスト (0は未確定セル)
- アルゴリズム: バックトラッキング + ビットマスク + MRVヒューリスティック
"""
def __init__(self, grid: List[List[int]]) -> None:
"""
初期化時に盤面をコピーし、行・列・3x3ブロックごとの使用済み数字をビットマスクに反映。
"""
assert len(grid) == N and all(len(row) == N for row in grid), "Grid must be 9x9"
self.grid = [row[:] for row in grid] # deepcopyして外部と分離
# 行・列・ブロックごとの使用済み数字を管理するマスク
self.row_mask = [0] * N
self.col_mask = [0] * N
self.box_mask = [0] * N
# 初期盤面をマスクに反映しつつ矛盾チェック
for r in range(N):
for c in range(N):
v = self.grid[r][c]
if v == 0:
continue # 空マスはスキップ
if not (1 <= v <= 9):
raise ValueError(f"Invalid value {v} at ({r},{c})")
if not self._placeable(r, c, v):
raise ValueError(f"Contradiction at ({r},{c}) with value {v}")
self._place(r, c, v)
# -------------------------------------------------------------------------
# 公開API
# -------------------------------------------------------------------------
def solve(self) -> bool:
"""
解を探索する。
解けたら True を返し、解の一例を self.grid に反映。
解が存在しない場合は False。
"""
# 次に探索すべきセルを選択（MRV: 候補が最小のセル）
pos = self._select_cell_with_min_candidates()
if pos is None:
# 未確定セルがない = 完成
return True
r, c = pos
# 選んだセルの候補を順に試す
for v in self._candidates(r, c):
self._place(r, c, v) # 値を仮置き
if self.solve(): # 再帰的に解く
return True # 解けたら即終了
self._remove(r, c, v) # 解けなければ元に戻す（バックトラック）
# 全候補試しても解けない → False
return False
def pretty(self) -> str:
"""
盤面を人間が読みやすい形式で返す。
例:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
"""
lines = []
for r in range(N):
row = []
for c in range(N):
row.append(str(self.grid[r][c]) if self.grid[r][c] != 0 else ".")
# 3列ごとに区切りを入れる
if c % 3 == 2 and c != N - 1:
row.append("|")
lines.append(" ".join(row))
# 3行ごとに区切り線を入れる
if r % 3 == 2 and r != N - 1:
lines.append("-" * (len(lines[-1])))
return "\n".join(lines)
# -------------------------------------------------------------------------
# 内部ユーティリティ
# -------------------------------------------------------------------------
@staticmethod
def _box_index(r: int, c: int) -> int:
"""
3x3ブロックのインデックスを計算。
左上から右下に向けて 0〜8 を割り当てる。
"""
return (r // 3) * 3 + (c // 3)
def _placeable(self, r: int, c: int, v: int) -> bool:
"""
(r,c) に値 v を置けるかどうかを判定。
行・列・ブロックのマスクをチェックして重複がないか確認。
"""
bit = 1 << v
return not (self.row_mask[r] & bit or
self.col_mask[c] & bit or
self.box_mask[self._box_index(r, c)] & bit)
def _place(self, r: int, c: int, v: int) -> None:
"""
(r,c) に値 v を置き、対応するマスクを更新する。
"""
bit = 1 << v
self.grid[r][c] = v
self.row_mask[r] |= bit
self.col_mask[c] |= bit
self.box_mask[self._box_index(r, c)] |= bit
def _remove(self, r: int, c: int, v: int) -> None:
"""
(r,c) の値 v を消去し、マスクも元に戻す。
バックトラック用。
"""
bit = 1 << v
self.grid[r][c] = 0
self.row_mask[r] &= ~bit
self.col_mask[c] &= ~bit
self.box_mask[self._box_index(r, c)] &= ~bit
def _candidate_mask(self, r: int, c: int) -> int:
"""
(r,c) に置ける候補のビットマスクを返す。
候補がなければ 0。
"""
used = self.row_mask[r] | self.col_mask[c] | self.box_mask[self._box_index(r, c)]
return FULL_MASK & ~used
def _candidates(self, r: int, c: int):
"""
(r,c) に置ける候補値を昇順で列挙するジェネレータ。
"""
mask = self._candidate_mask(r, c)
for v in range(1, 10):
if mask & (1 << v):
yield v
def _select_cell_with_min_candidates(self) -> Optional[Tuple[int, int]]:
"""
MRV (Minimum Remaining Values) ヒューリスティックを用いて、
未確定セルの中から候補数が最も少ないセルを選ぶ。
- 候補が0ならデッドエンド → 即リターン
- 候補が1なら即そのセルを返す（効率化）
- 未確定セルがなければ None を返す（完成）
"""
best: Optional[Tuple[int, int]] = None
best_count = 10 # 候補は最大9個なので初期値は10
for r in range(N):
for c in range(N):
if self.grid[r][c] != 0:
continue # 確定セルはスキップ
mask = self._candidate_mask(r, c)
cnt = mask.bit_count()
if cnt == 0:
return (r, c) # デッドエンドを検出
if cnt < best_count:
best_count = cnt
best = (r, c)
if cnt == 1: # これ以上小さくならない
return best
return best
# -------------------------------------------------------------------------
# 実行例
# -------------------------------------------------------------------------
if __name__ == "__main__":
# サンプル問題（0は空マス）
puzzle = [
[8, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 6, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 9, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 7, 0, 0, 0],
[0, 0, 0, 0, 4, 5, 7, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 3, 0],
[0, 0, 1, 0, 0, 0, 0, 6, 8],
[0, 0, 8, 5, 0, 0, 0, 1, 0],
[0, 9, 0, 0, 0, 0, 4, 0, 0],
]
sdk = Sudoku(puzzle)
ok = sdk.solve()
print(sdk.pretty())
if not ok:
print("\nNo solution found.")