【実践ガイド】ナンプレ 7 aiで最短解法を導くAI戦略とコード例

導入

7×7 のナンプレ（スパイクプレイン）は、従来型の 9×9 のスカンジナビアタイルと比べてシンプルで高速に解ける特徴を持っています。しかし、数多くのパズルを自動で最短解法（最小手数で唯一解になる経路）として報告・共有したい場合、単なるバックトラックだけでは時間が膨大になりがちです。
本記事では、AI（人工知能）を活用して「最短解法」を導き出す戦略と、Python で動く具体的なコード例を紹介します。実務で「ナンプレ 7」と共に使いこなすための実践的な知識を身につけてください。

1. ナンプレ 7 の基本と最短解法の定義

1.1 ナンプレ 7 のルール

• グリッドは 7×7。
• 1–7 の数字を各行・各列・各 1×7 のブロック（縦横に 7 セル）に重複なく入れる。
• スタートは既定の「部分的に埋められたピース」と「空白セル」の配列で表されます。

1.2 「最短解法」とは

• 手数＝「空白セルを 1 つずつ埋めて正解に到達するまでのステップ数」
• すべての合法手順を試し、最も少ない手数で唯一解に到達する経路を見つける。
• 9×9 では「最短経路問題」ですが、7×7 でも同様の最適化が有用です。

2. AI戦略の全体像

最短解を高速に求めるには、単なる列挙/バックトラックを超える戦略が必要です。以下は代表的な AI アプローチの組み合わせです。

最短解を保証するためには 「分枝限定法 + 制約充足」 の組み合わせが最も自然ですが、ヒューリスティックを加えることで多くのケースで探索を劇的に高速化できます。

3. 制約充足（CSP）で先読み

3.1 変数・領域設定

• 49 個のセルを変数 X_ij（i, j = 1〜7）に。
• 領域は 1〜7 の整数。
• 行・列・ブロックの「異質性」制約を追加（AllDifferent）。

3.2 変更可否の高速チェック

• Arc Consistency (AC‑3)：各隣接セル間で不可能な値を除外。
• 変更があれば再帰的に適用。
• これにより多数の矛盾を前もって排除し、探索木の枝を大幅に削減。

3.3 コード例：OR‑Tools CP‑SAT

from ortools.sat.python import cp_model

def solve_sudoku7(initial_grid):
    model = cp_model.CpModel()
    X = {}
    for i in range(7):
        for j in range(7):
            if initial_grid[i][j] == 0:
                X[i, j] = model.NewIntVar(1, 7, f'x_{i}_{j}')
            else:
                X[i, j] = model.NewIntVar(initial_grid[i][j], initial_grid[i][j], f'x_{i}_{j}')

    # 行・列・ブロック制約
    for k in range(7):
        model.AddAllDifferent([X[k, j] for j in range(7)])
        model.AddAllDifferent([X[i, k] for i in range(7)])
    for bi in range(0, 7, 1):
        for bj in range(0, 7, 1):
            block = [X[i, j] for i in range(bi, bi+7) for j in range(bj, bj+7)]
            model.AddAllDifferent(block)

    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
        return [[solver.Value(X[i, j]) for j in range(7)] for i in range(7)]
    else:
        return None

• この関数は**「ある一つの解」を返す**だけですが、model.AddAllDifferent が行・列・ブロックを保証しているため、最短手順を求めるベースとします。

4. ヒューリスティック検索で経路を最短化

CSP が解空間を絞り込んだ後、探索順序だけで手数を大きく削減できます。

4.1 先手探査（MVB – Minimum Value Branch）

• 最も制約が強いセル（可能値が最少のセル）を優先。
• これで分岐数が減るので、最短手数までの確率が上がります。

4.2 A* + ヒューリスティック

• cost = 手数（すでに決定した数字の数）
• h = 「空白セル数」または「制約残数の合計」を使った簡易推定
• f = g + h でソート。
• 9×9 でもよくある手法ですが、7×7 ではより高速に最短解を探せます。

4.3 実装例：Python で MVB と A* を混合

import heapq

def get_candidates(grid, i, j):
    used = set()
    used.update(grid[i])                  # 行
    used.update(grid[r][j] for r in range(7))  # 列
    start_r = (i//7)*7
    start_c = (j//7)*7
    for r in range(start_r, start_r+7):
        for c in range(start_c, start_c+7):
            used.add(grid[r][c])
    return [n for n in range(1, 8) if n not in used and n != 0]

def solve_min_steps(grid):
    # Initial priority queue: (f, g, grid, path)
    start = (0, 0, grid, [])
    pq = [start]
    seen = set()

    while pq:
        f, g, cur, path = heapq.heappop(pq)

        # すべて埋めると終了
        if all(cur[i][j] != 0 for i in range(7) for j in range(7)):
            return path

        # 1. 最も候補数が少ない空白セルを探す
        cell = min(((i, j) for i in range(7) for j in range(7) if cur[i][j]==0),
                   key=lambda pos: len(get_candidates(cur, *pos)), default=None)
        if cell is None: continue
        i, j = cell
        for val in get_candidates(cur, i, j):
            new_grid = [row[:] for row in cur]
            new_grid[i][j] = val
            new_path = path + [(i,j,val)]
            new_g = g + 1
            new_f = new_g + len([1 for r in range(7) for c in range(7) if new_grid[r][c]==0])
            state = tuple(tuple(r) for r in new_grid)
            if state in seen: continue
            seen.add(state)
            heapq.heappush(pq, (new_f, new_g, new_grid, new_path))
    return None

• 解法の手順（path）を取得できます。
• まずは「セル選択」＝MVB、続いて「総コスト最小」＝A* を同時に実行。

5. 分枝限定法で最短解を保証

5.1 原理

• 探索木を枝分かれさせ、既存の最短コストより大きい節点は即座に剪定。
• 解を発見したときは、そのコストを best として保持。

5.2 実装ポイント

• 再帰関数 dfs(grid, depth) で depth を現在の手数とする。
• depth >= best なら剪定。
• grid の空白セル数が 0 なら解を更新。

5.3 コード (再帰・剪定)

best_solution = None
best_depth = 49  # 上限

def dfs(grid, depth):
    global best_solution, best_depth
    if depth >= best_depth:
        return
    # すべて埋めたら更新
    if all(grid[i][j] != 0 for i in range(7) for j in range(7)):
        best_solution = [(i, j, grid[i][j]) for i in range(7) for j in range(7)]
        best_depth = depth
        return
    # もっと候補が少ないセル
    i, j = min(((i, j) for i in range(7) for j in range(7) if grid[i][j] == 0),
               key=lambda pos: len(get_candidates(grid, *pos)))
    for val in get_candidates(grid, i, j):
        new_grid = [row[:] for row in grid]
        new_grid[i][j] = val
        dfs(new_grid, depth + 1)

• dfs の depth が best_depth を上回る瞬間に枝が切れるため、最短解を必ず保証できる。

6. 実践テクニック：ハイブリッド戦略

1. 前処理：

   • AC‑3 で空白セルを減らす。
   • AllDifferent を適切に設定。

2. 探索：

   • ヒューリスティック（MVB）で分枝数を減らす。
   • A* で先読み・経路コストを可視化。

3. 剪定：

   • best_depth を実行中に更新し、枝分かれごとに比較。

4. 並列化：

   • multiprocessing でセルごとの候補ブランチを別プロセスで並行実行。
   • 効率的に CPU コアを活用できます。

5. 学習補助：

   • 既知の解法を収集し、CNN で「手順予測」を行うと、探索初期のセル選択がより最適化。

7. コード一式：最短解検索の統合

import heapq
from ortools.sat.python import cp_model

def get_candidates(grid, i, j):
    used = set()
    used.update(grid[i])                       # 行
    used.update(grid[r][j] for r in range(7))  # 列
    for r in range(7):
        for c in range(7):
            if grid[r][c] != 0:
                used.add(grid[r][c])
    return [n for n in range(1, 8) if n not in used]

# --------- 補助関数 ----------
def depth_first_search(grid, depth, best):
    global best_solution
    if depth >= best[0]:
        return
    empties = [(i,j) for i in range(7) for j in range(7) if grid[i][j]==0]
    if not empties:
        best[0] = depth
        best_solution = [(i,j,grid[i][j]) for i in range(7) for j in range(7)]
        return
    # MVB
    i, j = min(empties, key=lambda p: len(get_candidates(grid,*p)))
    for val in get_candidates(grid,i,j):
        new_grid = [row[:] for row in grid]
        new_grid[i][j] = val
        depth_first_search(new_grid, depth+1, best)

def minimal_solution(initial_grid):
    global best_solution
    best_solution = None
    best = [49]
    depth_first_search(initial_grid, 0, best)
    return best_solution

# --------- 使用例 ----------
sample = [
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0]
]
print("最短手数:", len(minimal_solution(sample)))

※ 本例は 空白全域 での最短解を求めるだけ。実際には開始時に数個の数字が埋められているケースを想定してください。

8. パフォーマンスチューニング

9. まとめ

• 7×7 ナンバーズは 9×9 に比べて「すべて埋める」場合に手数が大きく短くなるので、
  • アルゴリズムの設計が容易です。
• AC‑3 と A* を組み合わせたハイブリッド戦略がコアロジック。
• さらに 分枝限定法 を掛ければ必ず最短解を得られる。
• 実務には並列化や学習補助を追加することで、数千の問題を数秒以内に解くことが可能です。

これらの手法を自由に組み合わせて、あなたのナンバーズアプリに最短解探索レイヤーを組み込んでみてください。質問やチューニング疑問があればいつでもどうぞ！