ナンプレ ギガ 使わないで解く！メモリを節約した高速解法の秘訣

はじめに
数独（ナンプレ）は、9×9 のグリッドに数字を埋めるだけでなく、計算リソースやメモリに求められる最適化の良い演習題です。
昨今では「ギガ」―一括に候補を保持した巨大データ構造を使う方式―が一般的に紹介されることが増えました。しかし、実際に使う環境は PCのRAMに限幅があるものも多く、メモリを節約しながら高速に解く技術が求められます。この記事では、メモリ使用量を抑えつつ、走査速度を高める秘訣を段階的に解説します。

1. 従来の「ギガ」方式とその限界

1.1 何がギガなのか

典型的な実装では、各セルに対する可能数を 9 桁のビットで保持し、その全行・列・ブロックごとに共通にビットマスクを作成します。

• 行・列・ブロックごとのビットマスク: 3×3 スライディングウィンドウで 81 個のビット列を保持。
• 候補行列: 9×9 × 9 の3次元配列で、セルごとの候補をフラグで管理。

これらを一括でメモリ上に保持することで、探索時に候補を素早くフィルタでき、バックトラッキングが高速化されます。

1.2 メモリ消費の実態

• 行列配列: 9×9×9 で 729 個の bool → 729 バイト
• 行・列・ブロックビット: 約 81 個 × 9 バイト → 729 バイト
• その他オーバーヘッド: 100 バイト程度
  総計で 1.5KB 程度。
  実際のプログラム実装では、C++ の std::vector<bool> などが内部でメモリを増やすため、数十KB になるケースが多い。

1.3 なぜメモリを節約する必要があるか

1. 組込み環境: 例えば Raspberry Pi や IoT デバイス。
2. 大規模データセット: 複数のパズルを同時に解くバッチ処理。
3. 高速処理とメモリのトレードオフ: メモリがボトルネックになるとキャッシュミスが増え、計算速度が逆に落ちる。

2. メモリを節約しつつ高速にする戦略

ここでは「ビットマスク + 最適化探索」を組み合わせた方法を紹介します。

2.1 ビット演算を徹底する

• 候補ビット (uint16_t で 9bit を使用)
  • 1 で許可、0 で不許可。
• 行・列・ブロックマスク
  • rowMask[9], colMask[9], blockMask[9] を uint16_t で保持。

こうすることで、1 個のセルあたり 2 バイト に圧縮。

2.2 「先読み」付きバックトラッキング

バックトラッキングの際に次のセルの候補を 最小候補数 で選ぶ戦略 (MRV: Minimum Remaining Values)。
計算量を減らすため、次に埋めるセルを事前に決めておくと、探索木の枝刈りが大幅に増加します。

2.3 グローバル情報を保持しない

• 候補行列を完全にフラッシュせず、セルごとに必要になったら動的に算出します。
• これにより、行、列、ブロックマスクだけがメモリに残り、残りは 局所計算。

2.4 省メモリで高速化できる C++ テクニック

• constexpr で事前計算
  • 3×3 ブロックマスクの割り当てを constexpr で行い、実行時計算を削減。
• SIMD アクセラレーション
  • OpenMP で 4 コア以上を利用した場合、各コアが独立にセルを割り当て、ビット演算を SIMD で並列化。

3. 実装詳細 – パズルを 9×9 で解く

ここからは実際に使えるサンプルコードを示します。サンプルは C++17 で書かれています。

#include <array>
#include <cstdint>
#include <iostream>
#include <vector>

constexpr int N = 9;

// 9x9 パズルを 0 基点で格納。0 は未入力。
using Grid = std::array<std::array<uint8_t, N>, N>;

constexpr uint16_t ALL_BITS = 0x1FF; // 9 bits set

struct Solver {
    Grid board;
    std::array<uint16_t, N> rowMask{};
    std::array<uint16_t, N> colMask{};
    std::array<uint16_t, N> blkMask{};

    // 初期化
    Solver(const Grid& g) : board(g) {
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                uint8_t val = board[r][c];
                if (val) {
                    uint16_t bit = 1u << (val - 1);
                    rowMask[r] |= bit;
                    colMask[c] |= bit;
                    blkMask[(r/3)*3 + c/3] |= bit;
                }
            }
        }
    }

    // 最小候補数セルを探す
    bool findBest(int &bestR, int &bestC, uint16_t &cand) {
        int minCnt = 10; // 9より大きい初期値
        bestR = bestC = -1;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (!board[r][c]) {
                    uint16_t mask = rowMask[r] | colMask[c] | blkMask[(r/3)*3 + c/3];
                    uint16_t options = ALL_BITS & ~mask;
                    int cnt = __builtin_popcount(options);
                    if (cnt < minCnt) {
                        minCnt = cnt;
                        bestR = r; bestC = c; cand = options;
                        if (cnt == 1) return true; // 最短探索
                    }
                }
            }
        }
        return minCnt != 10;
    }

    bool solve() {
        int r, c; uint16_t options;
        if (!findBest(r, c, options)) return true; // 完了

        for (uint16_t opt = options; opt; opt &= opt - 1) {
            uint16_t bit = opt & -opt;         // 最下位ビット
            int val = __builtin_ctz(bit) + 1; // ビット位置 -> 値

            // 設定
            board[r][c] = val;
            rowMask[r] |= bit;
            colMask[c] |= bit;
            blkMask[(r/3)*3 + c/3] |= bit;

            if (solve()) return true; // 成功

            // 元に戻す
            board[r][c] = 0;
            rowMask[r] &= ~bit;
            colMask[c] &= ~bit;
            blkMask[(r/3)*3 + c/3] &= ~bit;
        }
        return false; // 失敗
    }

    void print() const {
        for (auto &row : board) {
            for (auto v : row) std::cout << int(v) << ' ';
            std::cout << '\n';
        }
    }
};

int main() {
    Grid board{{
        {5,3,0, 0,7,0, 0,0,0},
        {6,0,0, 1,9,5, 0,0,0},
        {0,9,8, 0,0,0, 0,6,0},

        {8,0,0, 0,6,0, 0,0,3},
        {4,0,0, 8,0,3, 0,0,1},
        {7,0,0, 0,2,0, 0,0,6},

        {0,6,0, 0,0,0, 2,8,0},
        {0,0,0, 4,1,9, 0,0,5},
        {0,0,0, 0,8,0, 0,7,9}
    }};

    Solver s(board);
    if (s.solve()) {
        std::cout << "Solution found:\n";
        s.print();
    } else {
        std::cout << "No solution.\n";
    }
}

3.1 コードポイント

1. ビットマスクのみで候補を管理
   • ALL_BITS は 0x1FF（9 個 1）。
   • mask = rowMask | colMask | blkMask で排除候補。
2. 最小候補セル MRV
   • findBest で全セルの候補数をカウントし、最小値を返す。
3. バックトラッキング
   • opt & -opt で最下位ビット（最小の候補）を取得。
4. メモリ使用量
   • rowMask, colMask, blkMask で 27 × 2 バイト = 54 バイト。
   • board は 81 バイト。

4. 高速化のさらに深掘り

4.1 並列探索

• 2 つの独立したバックトラッキングステップを同時に進めるため、分割統治 を行う。
• 例: 先頭の未埋めセルで分岐した 2 つの候補を別スレッドで探索。
• ただし、std::thread などを使うとメモリオーバーヘッドが増えるので、スレッド数は実機メモリに合わせて削減。

4.2 キャッシュローカリティの最適化

• 行列を連続した 1 次元配列に 変換し、連続アクセスで L1/L2 キャッシュヒット率を向上。
• 上記 C++ コードは std::array で連続領域を確保しており、ほぼ最適です。

4.3 ビット演算のハードウェアアクセラレーション

• x86 ベーシックで _mm_popcnt_u32 を使うとビット数カウントが高速化。
• 低スペックマシンでは __builtin_popcount で十分。

5. 実際のパフォーマンステスト

実行環境: 2.4 GHz i5, 8GB RAM
テストは 1000 様式の難易度・ミディアムをランダム生成し、解答完了までの平均時間を計算。

6. さらに深く踏み込むなら

1. ガードディクショナリ: 各セル毎に 9 桁のビットマスクを uint64_t で保持し、シフト演算で候補を更新。
2. 最頻数候補 (LCM)：過去のデータベースを使い、頻度が高い数字を優先。
3. 機械学習 で次に埋めるセルの順序を予測し、探索枝刈り率を 10％ 以上向上。

7. まとめ

• メモリを極力抑える: 行・列・ブロックだけの uint16_t マスクで 54 バイト。
• 探索をスリム化: MRV で最小候補セルを先に決定し、枝刈りを最大化。
• 高速に保つ: ビット演算とコンパイラ最適化で数百ミリ秒以内。

これらを組み合わせれば「ギガ」方式を使わずに、組込みや高負荷環境でも快適にナンプレを解くことができます。
ぜひ実装に取り組み、必要に応じて並列化やキャッシュ最適化も試してみてください。

一歩先を行く解法は、単なるメモリ節約ではなく、データ構造の選定と探索戦略の両面の最適化が鍵です。
皆さんの次のナンプレプロジェクトが高速・低メモリで実装できることを願っています！