博士

ロボ子、数独って知ってるかのじゃ？

ロボ子

はい、知っています。数字を埋めていくパズルですよね。

博士

そうじゃ。実は数独、グラフ理論や抽象代数学と深〜く関わっているのじゃ。

ロボ子

えっ、そうなんですか？ただのパズルだと思っていました。

博士

グラフ理論では、数独の盤面をグラフとして表現するのじゃ。各セルをグラフの頂点に対応させて、同じ行、列、3x3の領域にあるセル同士を辺で結ぶ。すると、数独を解くことは、このグラフを9色で彩色できるかどうかの問題になるのじゃ。

ロボ子

なるほど！頂点彩色問題として捉えるんですね。貪欲法やバックトラッキングで解けるんですか？

博士

その通り！貪欲法やバックトラッキングなどの頂点彩色アルゴリズムを適用することで、数独の解を探索できるのじゃ。

ロボ子

面白いですね！抽象代数学ではどうなるんですか？

博士

抽象代数学では、数独の問題を多項式方程式系として表現するのじゃ。各セルに対応する変数を導入し、数独のルールを多項式方程式で表現する。

ロボ子

多項式方程式…難しそうですね。

博士

例えば、各セルに入る数字は1から9のいずれかであるという制約は、多項式(x_i-1)(x_i-2)...(x_i-9)=0で表現できるのじゃ。各行、列、領域に同じ数字が重複して入らないという制約も、和と積に関する多項式で表現できる。

ロボ子

なるほど、制約を数式で表すんですね。

博士

そうじゃ。初期盤面で既に数字が埋まっているセルについては、x_j-a_j=0という多項式を追加する。これらの多項式からなる方程式系に対して、Buchbergerのアルゴリズムを適用してグレブナー基底を計算するのじゃ。

ロボ子

グレブナー基底…初めて聞きました。

博士

グレブナー基底は、多項式系の解を変化させずに、より解きやすい形に変形するものじゃ。数独に一意解が存在する場合、グレブナー基底は81個の線形多項式からなり、そこから数独の解を読み取ることができるのじゃ。

ロボ子

へー！すごいですね。具体的にどうやって解くんですか？

博士

シドク(4x4の盤面)を例にすると、16個の変数、行、列、領域の和と積に関する多項式、初期盤面の情報からなる多項式方程式系を構築する。そして、コンピュータ代数システム(Matlabなど)を用いてBuchbergerのアルゴリズムを実行し、グレブナー基底を計算するのじゃ。得られたグレブナー基底から、シドクの解を読み取る。

ロボ子

Matlabを使うんですね。なんだか本格的ですね。

博士

数独って奥が深いじゃろ？

ロボ子

はい、単なるパズルだと思っていたのが覆されました！

博士

ちなみに、数独を解くプログラムを作ろうとして、数独が解けずに一日が終わることを、プログラマの間では「数独詰み」と言うらしいぞ。

ロボ子

それは、あるあるですね！