数独解析アルゴリズム

数独解析ツールを作成してしまいました。
https://github.com/takishita2nd/sudokuGUI
ここでは、数独を解析するためのアルゴリズムをまとめてみました。

解析パターン１

数独のルールとして、オレンジのマスに注目した場合、黄色の範囲（縦９マス、横９マス、３×３の９マス）の中に同じ数字が存在してはならない、となります。
この確認を行うために以下の配列を用意します。

bool[] value = new bool[9] { false, false, false, false, false, false, false, false, false };

boolの配列の添え字0~8はそれぞれ数字の1~9に対応します。
黄色の範囲を全てチェックし、その中に存在する数字に対応するbool配列の値をtrueに設定します。
全てチェックを行った結果、bool配列の中に一つだけfalseの物があれば、その添え字に対応する数字が、オレンジのマスの数字になります。

フローチャートはこのようになります。

解析パターン２

以下の様な状態の場合、

３という数字に注目すると、青い部分には、数独のルールから逸脱するため、３を置くことができません。

このとき、赤い部分に注目すると、空いているマスは一つだけになります。この場所に３の数字が入ることが分かると思います。

このパターンを処理するため、以下9×9のbool型の二次元配列データを用意します。

bool[,] value = new bool[9, 9];
for (int i = 0; i < 9; i++)
{
    for (int j = 0; j < 9; j++)
    {
        value[i, j] = false;
    }
}

一つの数字について、置くことができないマスを全てtrueに設定します。
true=1,false=0として可視化すると、以下の様になります。

次に3×3の9マスを確認し、一つだけfalseの場所(緑の箇所)を探します。このfalseの部分のマスの値がその数字で確定します。
これを1~9の数字に対して行います。

フローチャートは以下の様になります。

解析パターン３（仮置きロジック）

以下の様なケースの場合、今までの解析パターンではこれ以上解析することができません。

2の数字に着目した場合、オレンジの場所のどちらかに2が入ることが分かります。

例えば、下のオレンジの箇所に2を置いた場合、青い箇所に2を置くことになりますが、縦のラインにすでに2が入っているため、置くことができません。すなわち、この場所に2を置くことは誤りである事が分かります。

以下のように2を置くことでこの問題を解くことができます。

これを実装するためには、以下の処理を考える必要があります。

• 仮置きロジックを適用するマスを抽出する。
• 矛盾があるかどうかを確認する。
• 矛盾があった場合、そのデータを廃棄し、仮置きロジック前の状態に戻すため、解析中のデータの複製を作る。
• 仮置きロジック中に再び仮置きロジックを使用するケースもあり得るので、再帰的に仮置きロジックを実行できるようにする。

仮置き対象の抽出

仮置き対象の抽出は以下の様に考えます。最も候補が少ない箇所が仮置きロジックの対象として適当と思われます。

矛盾があるかの確認

矛盾があるかどうかの確認は、全てのマスに対して置ける数字の候補を確認し、候補が存在しない場合、矛盾が発生したと考えます。
以下のデータを用意します。

bool[] value = new bool[9] { false, false, false, false, false, false, false, false, false };

全てのマスに対して縦9マス、横9マス、3×3の9マスに対して存在する数字を確認し、上の配列の対応する箇所をtrueに設定します。
配列全てtrueとなった場合、そのマスに置ける数字が存在しないことになり、矛盾が発生したと判断することができます。

仮置きロジック

これらの処理を使って、仮置きロジックを作成します。

最終的に数独解析アルゴリズムはこうなります。