C++で数独を解く！バックトラッキングによる数独ソルバーの実装方法

9×9のマス目に並んだ数字のパズル「数独（Sudoku）」を、プログラムで自動的に解く方法を解説します。数独は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 を返します。

• isPresentInBox(boxStartRow, boxStartCol, num)：3×3ブロック内に num が存在するか確認するメソッド。boxStartRow から3行、boxStartCol から3列の範囲を走査して判定します。

• findEmptyPlace(row, col)：まだ数字が入っていない（値が0の）空きマスを探し、その位置を返すメソッドです。

• isValidPlace(row, col, num)：num がその場所（行・列・3×3ブロックのいずれにも存在しないこと）に置けるかどうかを判定するメソッドです。

• solveSudoku()：本体となる再帰的な解法メソッド。空きマスがなければ true を返して完了とし、空きマスがあれば1〜9の数字について isValidPlace で検証しながら配置し、再帰的に解き進めます。失敗した場合はマスを0に戻して次の数字を試します。

C++での実装例

以下にC++による実際のコードを示します。空きマスは0で表現しています。

#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ブロックのどこにも存在しない場合に有効
    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)){ // 検証してOKならグリッドに配置
          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

このように、バックトラッキングを活用することで、数独のような制約充足問題を効率的に解くプログラムを実装できます。