C++で部分的に埋められた数独グリッドを解くプログラム(バックトラッキング法)

ここでは、一部のマスのみが埋められた数独グリッドをC++で解く方法を解説します。数独とは9×9の数字グリッドであり、全体はさらに3×3のボックスに分割されています。数独を解くためには、以下のルールを守る必要があります。

• 使用する数字は1から9までです。
• 同じ行・同じ列・同じ3×3ボックス内に、同じ数字を重複して配置することはできません。

バックトラッキングによる解法の考え方

本記事ではバックトラッキング(バックトラック)アルゴリズムを使用して数独を解きます。空きマスに数字を仮に置いた後、その配置がルール上妥当かどうかを検証します。もし配置が不正であれば別の数字を試し、1〜9のすべての数字を試しても有効な数字が見つからない場合は、直前の選択に戻って(バックトラックして)別の候補を探索します。

実装の手順

この問題を解くために、以下の関数を定義します。

isPresentInCol(col, num)

• 指定した列colに数字numが存在するかを確認します。
• グリッド内の各行rについて走査し、grid[r][col]がnumと一致すればtrueを返します。
• 見つからなければfalseを返します。

isPresentInRow(row, num)

• 指定した行rowに数字numが存在するかを確認します。
• 各列cについて走査し、grid[row][c]がnumと一致すればtrueを返します。
• 見つからなければfalseを返します。

isPresentInBox(boxStartRow, boxStartCol, num)

• 指定した3×3ボックス内に数字numが存在するかを確認します。
• boxStartRowから3行分、boxStartColから3列分を走査し、該当する数字があればtrueを返します。

findEmptyPlace(row, col)

• グリッド内の空きマス(値が0の場所)を探し、参照渡しで行と列を更新します。
• 空きマスが存在すればtrue、存在しなければfalseを返します。

isValidPlace(row, col, num)

• 数字numが同じ行・列・現在の3×3ボックスのいずれにも存在しない場合にtrueを返します。

solveSudoku()

• 空きマスがなくなればtrueを返します(解決完了)。
• 数字1〜9について順番に試し、isValidPlaceが成立すればその数字を置いて再帰的にsolveSudoku()を呼び出します。
• 再帰呼び出しが失敗した場合は、そのマスを0に戻して次の数字を試します。
• すべて試しても解けなければfalseを返します。

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){
    // 指定した3x3ボックスにnumが存在するか確認
    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, 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}

出力

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ボックスごとの重複チェックを組み合わせ、無効な配置を素早く検知して探索範囲を絞り込むことがポイントです。計算量は最悪の場合指数オーダーになりますが、実際の数独のような制約の多い問題では高速に動作します。