はじめに
前回までの記事で、数独（ナンプレ）の基本的なルールを理解し、 VBAで数独盤面を表現し、基本的なチェック機能（行、列、ブロックの重複チェック）を実装するまでを解説しました。今回は、いよいよ数独を解くための肝となる「探索アルゴリズム」の実装に踏み込みます。数独のようなパズルを解くアルゴリズムとしては、「バックトラッキング（Backtracking）」と呼ばれる手法が一般的であり、VBAでも比較的容易に実装できます。このバックトラッキングを理解し、数独を自動で解くVBAプログラムを完成させましょう。
バックトラッキングとは？
バックトラッキングは、問題解決のための探索アルゴリズムの一つです。簡単に言うと、「可能性のある解を一つずつ試していき、行き詰まったら一つ前の状態に戻って別の可能性を試す」という方法です。数独に当てはめると、以下のようになります。
1. **空いているマスを探す:** 数独盤面で、まだ数字が埋まっていないマス（通常は「0」で表現）を探します。
2. **数字を試す:** 見つけた空きマスに、1から9までの数字を順番に当てはめてみます。
3. **ルールに合致するかチェック:** 当てはめた数字が、数独のルール（行、列、3×3ブロックで数字が重複しない）に合致するかどうかをチェックします。
4. **合致した場合:** ルールに合致したら、その数字を確定させ、次の空きマスを探しに行きます。
5. **合致しなかった場合:** ルールに合致しなかったら、その数字は不適切と判断し、次の数字（例えば、1を試してダメなら2を試す）を試します。
6. **行き詰まった場合:** 1から9までの全ての数字を試してもルールに合致する数字が見つからなかった場合、それは「行き詰まり」です。この場合、一つ前のマスに戻り、そこで試していた数字を一つ進めて（例えば、前のマスで「3」を試していたなら「4」を試す）、再度探索を続けます。
7. **全てのマスが埋まったら完了:** このプロセスを繰り返し、全てのマスが埋まり、かつ全てのルールを満たしていれば、数独は解けたことになります。
この「行き詰まったら戻る」という動作が、バックトラッキングの核心です。再帰処理（関数が自分自身を呼び出すこと）を用いると、このバックトラッキングをエレガントに実装できます。
VBAでの実装：再帰関数によるバックトラッキング
数独を解くためのVBAコードは、主に以下の要素で構成されます。
* **数独盤面を表す2次元配列:** 前回同様、`Dim board(1 To 9, 1 To 9) As Integer` のような配列を使用します。
* **空きマスを探す関数:** 現在の盤面で、次に埋めるべき空きマス（値が0のマス）の行と列を返す関数です。
* **数字がルールに合致するかチェックする関数:** 指定したマスに指定した数字を入れることが、行、列、ブロックのルールに違反しないかを確認する関数です。これは前回実装したものを再利用します。
* **バックトラッキングを実行する再帰関数:** これがメインの関数です。空きマスを見つけ、数字を試して、ルールチェックを行い、必要に応じて自分自身を呼び出す（再帰）処理を行います。
それでは、具体的なコードを見ていきましょう。
1. 空きマスを探す関数 (FindEmptyCell)**
この関数は、数独盤面を左上から右下へとスキャンし、最初に見つかった空きマス（値が0）の行と列を返します。もし空きマスが一つも見つからなければ、盤面が全て埋まっていることを示す特殊な値を返します。
‘ 指定された盤面で、次に見つかる空きマス(0)の行と列を返す
‘ 見つからなければ、行と列に0をセットしてTrueを返す
‘ 見つかれば、その行と列をセットしてFalseを返す
Function FindEmptyCell(ByRef board() As Integer, ByRef row As Integer, ByRef col As Integer) As Boolean
Dim r As Integer, c As Integer
FindEmptyCell = False ‘ 初期値は、空きマスが見つからない（完了）とする
For r = 1 To 9
For c = 1 To 9
If board(r, c) = 0 Then
row = r
col = c
FindEmptyCell = True ‘ 空きマスが見つかった
Exit Function
End If
Next c
Next r
End Function
2. 数字の妥当性チェック関数 (IsValid)**
この関数は、前回実装したものを再利用します。指定された行、列、数字が、数独のルール（行、列、3×3ブロックでの重複がないこと）に合致するかどうかを判定します。
‘ 指定された行(row)、列(col)に、指定された数字(num)が有効かどうかをチェックする
Function IsValid(ByRef board() As Integer, ByVal row As Integer, ByVal col As Integer, ByVal num As Integer) As Boolean
Dim r As Integer, c As Integer
‘ 行のチェック
For c = 1 To 9
If board(row, c) = num Then
IsValid = False
Exit Function
End If
Next c
‘ 列のチェック
For r = 1 To 9
If board(r, col) = num Then
IsValid = False
Exit Function
End If
Next r
‘ 3×3ブロックのチェック
Dim startRow As Integer, startCol As Integer
startRow = Int((row – 1) / 3) * 3 + 1
startCol = Int((col – 1) / 3) * 3 + 1
For r = startRow To startRow + 2
For c = startCol To startCol + 2
If board(r, c) = num Then
IsValid = False
Exit Function
End If
Next c
Next r
‘ 全てのチェックを通過したら有効
IsValid = True
End Function
3. バックトラッキングを実行する再帰関数 (SolveSudoku)**
これが数独を解くためのメインの関数です。
* まず `FindEmptyCell` を呼び出して、空きマスを探します。
* もし空きマスが見つからなければ（`FindEmptyCell` が `False` を返したら）、数独は解けたので `True` を返して終了します。
* 空きマスが見つかったら、そのマスに1から9までの数字を順番に試します。
* 各数字について `IsValid` 関数でルールチェックを行います。
* ルールに合致する数字が見つかったら、その数字をマスにセットし、さらに `SolveSudoku` 関数自身を再度呼び出します（これが再帰）。
* 再帰呼び出しが `True` を返した場合（つまり、その数字を基点とした探索で数独が解けた場合）、現在の `SolveSudoku` 関数も `True` を返します。
* もし、試した数字で再帰呼び出しが `False` を返した場合（つまり、その数字では数独が解けなかった場合）、そのマスにセットした数字を元に戻し（0にクリアし）、次の数字を試します。
* 1から9までの全ての数字を試しても解けなかった場合は、この `SolveSudoku` 関数は `False` を返します。これにより、前の再帰呼び出し元（一つ前のマス）に「行き詰まり」が伝わり、そちらで別の数字を試すことになります。
‘ 数独盤面を解くための再帰関数
‘ 盤面(board)を引数に取り、解けたらTrue、解けなければFalseを返す
Function SolveSudoku(ByRef board() As Integer) As Boolean
Dim row As Integer, col As Integer
‘ 空きマスを探す
If Not FindEmptyCell(board, row, col) Then
SolveSudoku = True ‘ 空きマスがなければ、解けたということ
Exit Function
End If
‘ 見つかった空きマスに1から9までの数字を試す
Dim num As Integer
For num = 1 To 9
‘ 数字がルールに合致するかチェック
If IsValid(board, row, col, num) Then
‘ 合致したら、その数字をセットしてみる
board(row, col) = num
‘ 再帰的に次のマスを解きにいく
If SolveSudoku(board) Then
SolveSudoku = True ‘ 解けたらTrueを返す
Exit Function
End If
‘ もし、この数字で解けなかった場合（再帰呼び出しがFalseを返した場合）は、
‘ 元に戻して、次の数字を試す（バックトラッキング）
board(row, col) = 0
End If
Next num
‘ 1から9までのどの数字も試しても解けなかった場合
SolveSudoku = False
End Function
4. メイン処理 (SolveButton_Clickなど)**
この `SolveSudoku` 関数を呼び出すためのサブルーチンを用意します。ここでは、Excelシート上のセルに数独盤面が入力されていることを想定し、それを2次元配列に読み込み、解いた後、再度シートに書き戻す処理を行います。
‘ 数独を解くためのトリガーとなるサブルーチン
Sub SolveCurrentSudoku()
Dim ws As Worksheet
Set ws = ThisWorkbook.ActiveSheet ‘ アクティブなシートを対象とする
Dim board(1 To 9, 1 To 9) As Integer
Dim r As Integer, c As Integer
‘ シートから盤面を配列に読み込む (A1からI9を想定)
On Error Resume Next ‘ エラー処理を追加
For r = 1 To 9
For c = 1 To 9
‘ セルの値が数値であることを確認
If IsNumeric(ws.Cells(r, c).Value) Then
board(r, c) = CInt(ws.Cells(r, c).Value)
Else
MsgBox “セル(” & r & “,” & c & “)の値が不正です。数値を入力してください。”, vbCritical
Exit Sub
End If
Next c
Next r
On Error GoTo 0
‘ 数独を解く
If SolveSudoku(board) Then
‘ 解けた場合、シートに結果を書き戻す
For r = 1 To 9
For c = 1 To 9
ws.Cells(r, c).Value = board(r, c)
Next c
Next r
MsgBox “数独が解けました！”, vbInformation
Else
MsgBox “この数独は解けません。”, vbExclamation
End If
End Sub
この `SolveCurrentSudoku` サブルーチンを、Excelシート上に配置したボタンなどに登録すれば、ワンクリックでアクティブなシートの数独を自動で解くことができます。
実務アドバイス
* **エラーハンドリングの強化:** 上記のコードでは基本的なエラーハンドリングのみですが、実務では、入力値のバリデーション（1～9以外の数字や文字列が入力されていないか）、シートの存在チェック、セルの範囲チェックなどをより厳密に行う必要があります。
* **パフォーマンスの最適化:** 非常に難しい数独や、解けない（または解くのに時間がかかる）数独の場合、VBAの実行速度が遅くなることがあります。
* `Application.ScreenUpdating = False` と `Application.Calculation = xlCalculationManual` をコードの冒頭に記述し、実行後に元に戻すことで、画面描画と自動計算をオフにし、処理速度を向上させることができます。
* より高度な最適化としては、盤面を配列で操作する際に、ループ回数を減らす、無駄な処理を省く、といった工夫が考えられます。
* **ユーザーインターフェース (UI) の改善:** 解答結果をシートに書き戻すだけでなく、元の数字と解答された数字を色分けで表示したり、解けない場合にその理由（例えば、初期盤面がおかしいなど）をユーザーに伝えたりするUIを検討すると、より使いやすいツールになります。
* **難易度判定:** 数独の「難易度」は、解くために必要なバックトラックの回数や、試行錯誤の深さなどで決まります。もし可能であれば、解く過程でバックトラックの回数をカウントし、その回数に応じて難易度を判定する機能を追加することも考えられます。
* **複数の解法:** バックトラッキングは数独を解くための代表的なアルゴリズムですが、他にも「論理パズル解法」をVBAで実装するというアプローチもあります。これは「もしこのマスが1なら、このマスは2になるはずだ…」といった論理的な推論をコード化するもので、より人間が解くプロセスに近くなります。ただし、実装は非常に複雑になります。
まとめ
今回は、VBAで数独を自動で解くための核となる「バックトラッキング」アルゴリズムを、再帰関数を用いて実装しました。空きマスを探し、数字を試してルールチェックを行い、行き詰まったら戻るという一連の流れをVBAコードに落とし込むことで、数独ソルバーの主要部分が完成しました。
このバックトラッキングの考え方は、数独だけでなく、迷路、ナップサック問題、組み合わせ最適化問題など、様々な探索問題を解くための強力な手法です。VBAでこのアルゴリズムを理解し、実装できたことは、プログラミングスキルの大きな向上に繋がるはずです。
次回は、この数独ソルバーをさらに発展させるための応用編（例えば、難易度設定や、解答のステップ表示など）について触れるかもしれません。ぜひ、今回学んだコードを基に、ご自身のExcel VBAプロジェクトに活用してみてください。
