数独（ナンプレ）を解くアルゴリズム：バックトラッキング法をC++で実装する方法

はじめに

本記事では、数独（Sudoku／ナンプレ）として知られる有名な数字パズルを、コンピュータプログラムで解く方法を解説します。数独は 9×9 の数字グリッドで構成され、盤面全体はさらに 3×3 のブロック（ボックス）に分割されています。

数独を解く際には、以下の基本的なルールに従う必要があります。

• 使用する数字は 1〜9 のみです。
• 同じ行、同じ列、そして同じ 3×3 ブロック内に、同じ数字を重複して配置することはできません。

バックトラッキングによるアプローチ

ここではバックトラッキング（後戻り法）アルゴリズムを用いて数独を解きます。バックトラッキングの流れは以下のとおりです。

1. 空きセルに数字を 1 つ置き、その配置がルールに適合しているか（妥当か）を検証します。
2. 配置が妥当でなければ、別の数字を試します。
3. 1〜9 のすべての数字を試しても有効な数字が見つからない場合、直前のセルに戻って（バックトラックして）別の選択肢を探索します。

この「試しては戻る」処理を繰り返すことで、最終的に解へたどり着きます。

入力と出力

入力:
9×9 の行列を数独グリッドとして受け取ります。あらかじめいくつかの値が
盤面に配置されており、空きマスは 0 で表されます。

出力:
すべてのマスが埋まった完成版の数独グリッド。解が存在しない場合は false を返します。

3 1 6  | 5 7 8  | 4 9 2
5 2 9  | 1 3 4  | 7 6 8
4 8 7  | 6 2 9  | 5 3 1
------------------------
2 6 3  | 4 1 5  | 9 8 7
9 7 4  | 8 6 3  | 1 2 5
8 5 1  | 7 9 2  | 6 4 3
------------------------
1 3 8  | 9 4 7  | 2 5 6
6 9 2  | 3 5 1  | 8 7 4
7 4 5  | 2 8 6  | 3 1 9

アルゴリズムの詳細

数独ソルバーは、以下の補助関数を組み合わせて構成します。擬似コードで順番に見ていきましょう。

isPresentInCol(col, num)

入力: 列（col）と調べたい数字（num）。
出力: 指定した列にその数字が存在すれば true。

Begin
    for each row r in the grid, do
        if grid[r, col] = num, then
            return true
    done
    return false otherwise
End

isPresentInRow(row, num)

入力: 行（row）と調べたい数字（num）。
出力: 指定した行にその数字が存在すれば true。

Begin
    for each column c in the grid, do
        if grid[row, c] = num, then
            return true
    done
    return false otherwise
End

isPresentInBox(boxStartRow, boxStartCol, num)

入力: 3×3 ブロックの開始行・開始列と、調べたい数字。
出力: そのブロック内に数字が存在すれば true。

Begin
    for each row r in boxStartRow to next 3 rows, do
        for each col c in boxStartCol to next 3 columns, do
            if grid[r, c] = num, then
                return true
        done
    done
    return false otherwise
End

findEmptyPlace(row, col)

入力: グリッド上の行と列。
出力: grid[row, col] が空（0）なら true、そうでなければ false。

Begin
    for each row r in the grid, do
        for each column c in the grid, do
            if grid[r, c] = 0, then
                return true
        done
    done
    return false
End

isValidPlace(row, col, num)

入力: 行・列と、チェックしたい数字。
出力: その位置への数字の配置が妥当であれば true。

Begin
    if isPresentInRow(row, num) and isPresentInCol(col, num) and
    isPresentInBox(row – row mod 3, col – col mod 3, num) all are false, then
        return true
End

つまり、行・列・3×3 ブロックのどこにもその数字が存在しなければ、その配置は妥当であると判定します。

solveSudoku(数独グリッド)

入力: 未解決の数独グリッド。
出力: 解決後のグリッド。

Begin
    if no place in the grid is empty, then
        return true
    for number 1 to 9, do
        if isValidPlace(row, col, number), then
            grid[row, col] := number
            if solveSudoku = true, then
                return true
            grid[row, col] := 0
    done
    return false
End

すべてのマスが埋まれば解決完了（true）、そうでなければ 1〜9 の数字を順に試し、再帰的に次の空きマスへ進みます。失敗した場合はセルを 0 に戻してバックトラックします。

C++ による実装例

#include <iostream>
#define N 9
using namespace std;

int grid[N][N] = {
    {3, 0, 6, 5, 0, 8, 4, 0, 0},
    {5, 2, 0, 0, 0, 0, 0, 0, 0},
    {0, 8, 7, 0, 0, 0, 0, 3, 1},
    {0, 0, 3, 0, 1, 0, 0, 8, 0},
    {9, 0, 0, 8, 6, 3, 0, 0, 5},
    {0, 5, 0, 0, 9, 0, 6, 0, 0},
    {1, 3, 0, 0, 0, 0, 2, 5, 0},
    {0, 0, 0, 0, 0, 0, 0, 7, 4},
    {0, 0, 5, 2, 0, 6, 3, 0, 0}
};

bool isPresentInCol(int col, int num) {     // num が列に存在するか判定
    for (int row = 0; row < N; row++)
        if (grid[row][col] == num)
            return true;
    return false;
}

bool isPresentInRow(int row, int num) {     // num が行に存在するか判定
    for (int col = 0; col < N; col++)
        if (grid[row][col] == num)
            return true;
    return false;
}

bool isPresentInBox(int boxStartRow, int boxStartCol, int num) {   // num が 3x3 ブロックに存在するか判定
    for (int row = 0; row < 3; row++)
        for (int col = 0; col < 3; col++)
            if (grid[row+boxStartRow][col+boxStartCol] == num)
                return true;
    return false;
}

void sudokuGrid() {     // 解決後の数独グリッドを出力
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if(col == 3 || col == 6)
                cout << " | ";
            cout << grid[row][col] <<" ";
        }

        if(row == 2 || row == 5) {
            cout << endl;
            for(int i = 0; i<N; i++)
                cout << "---";
        }
        cout << endl;
    }
}

bool findEmptyPlace(int &row, int &col) {     // 空きマスを探し、行と列を更新
    for (row = 0; row < N; row++)
        for (col = 0; col < N; col++)
            if (grid[row][col] == 0) // 0 は空きマスを表す
                return true;
    return false;
}

bool isValidPlace(int row, int col, int num) {
    // 行・列・現在の 3x3 ブロックのいずれにも num が存在しない場合に有効
    return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num);
}

bool solveSudoku() {
    int row, col;
    if (!findEmptyPlace(row, col))
        return true;     // すべてのマスが埋まった
    for (int num = 1; num <= 9; num++) {     // 有効な数字は 1〜9
        if (isValidPlace(row, col, num)) {     // 妥当性を確認し、問題なければグリッドに配置
            grid[row][col] = num;
            if (solveSudoku())     // 再帰的に残りのマスを解く
                return true;
            grid[row][col] = 0;     // 条件を満たさない場合は未割り当てに戻す（バックトラック）
        }
    }
    return false;
}

int main() {
    if (solveSudoku() == true)
        sudokuGrid();
    else
        cout << "No solution exists";
}

実行結果

3 1 6  | 5 7 8  | 4 9 2
5 2 9  | 1 3 4  | 7 6 8
4 8 7  | 6 2 9  | 5 3 1
------------------------
2 6 3  | 4 1 5  | 9 8 7
9 7 4  | 8 6 3  | 1 2 5
8 5 1  | 7 9 2  | 6 4 3
------------------------
1 3 8  | 9 4 7  | 2 5 6
6 9 2  | 3 5 1  | 8 7 4
7 4 5  | 2 8 6  | 3 1 9

まとめ

バックトラッキング法を使えば、数独のような制約充足問題をシンプルなコードで解くことができます。行・列・3×3 ブロックの重複チェックを行う補助関数と、再帰的な探索を組み合わせることがポイントです。ただし、最悪の場合には計算量が増大するため、候補となる数字を絞り込むヒューリスティクス（例：配置可能な数字が最も少ないマスから埋める手法など）を組み合わせると、より高速に解けるようになります。