Counting, Symmetries and Equivalence Classes of Sudoku Grids

大いなる数独パズル・ハント

あなたは、81の部屋がある巨大な屋敷を、9種類の異なる家具で埋め尽くすあらゆる方法を数えようとしている探偵だと想像してください。しかし、そこには非常に厳しいルールがあります。すべての行、すべての列、そしてすべての3x3の部屋において、必ず各家具のタイプが正確に一つずつ存在しなければなりません。これが数独の世界です。数独は何百万人もの人々を魅了してきましたが、数学者にとって、それは単なるゲームではありません。それは巨大な組合せ論の迷路なのです。彼らは知りたいと考えています。一体、どれほど多くのユニークで完全な「屋敷（あるいはグリッド）」が存在するのか？ そしてより重要なのは、家全体を回転させたり、家具の名前を入れ替えたりすることを無視した場合、本当に異なる（本質的に異なる）グリッドはいくつあるのかということです。

この問題を解くために、数学者は「群論」という強力なツールを使用します。これは本質的に対称性の研究です。対称性とは、まるで魔法の鏡のようなものです。雪の結晶を回転させたり、トランプを裏返したりすると、一瞬見た目は変わるかもしれませんが、それは根本的には同じ物体です。数独の世界では、数字を入れ替えたり（例えば、すべての1を2に、2を1に入れ替えるなど）、行や列をシャッフルしたりすることで、あるグリッドを別のグリッドに変えられる場合、それら2つのグリッドは「双子」であるとみなされます。大きな疑問は、ユニークで非双子的な（本質的に異なる）グリッドを数えると、いくつになるのかということです。数十年にわたり、その答えは力任せのコンピュータによる計算によって導き出されてきましたが、その手順は明確で論理的な道筋というよりは、雑多なトリックの山のように感じられました。

論文の発見：隠されたパターンの発見

この論文において、フェルナンダ・ペレイラは、数独のカウント問題における特定の、非常にトリッキーな部分に新たな視点を持ち込んでいます。彼女は、グリッドの「最初のバンド（第1帯）」、つまり上部の3行に焦点を当てています。以前の研究者であるフェルゲンハウアーとジャービスは、これら上部行のバンドには正確に44の異なるタイプが存在することをすでに突き止めていました。しかし、彼らがこの44という数字に到達したのは、5つの異なる「簡約（リダクション）」による長く複雑な連鎖を適用した結果でした。それは、玉ねぎの皮を一層ずつ剥いていくようなもので、各層ごとに異なる特定のテクニックを必要としました。結果は正しかったのですが、この44という数字は、深い意味を持たない、長い曲がりくねった道の上のランダムな立ち寄り地点のように感じられました。

ペレイラの論文は、44はランダムな偶然ではないと主張しています。それは、根本的な構造的真実であると述べています。彼女は、問題を層ごとに剥いていくのではなく、新しいレンズを通して数独のグリッドを見ることを提案しています。それが「列分割（カラム・パーティション）」です。

グリッドの上部3行を、3つの別々のボックスとして想像してみてください。各ボックス内では、3つの列に含まれる数字が、特定の3つの数字の「チーム」を形成します。例えば、最初のボックスでは、第1列が{1, 4, 7}、第2列が{2, 5, 8}、第3列が{3, 6, 9}となるかもしれません。このグルーピングを「分割（パーティション）」と呼びます。ペレイラの画期的なアイデアは、数独グリッドのバンド全体の複雑さは、これら3つの数字の「チーム」の単純なリストへと集約できるという点にあります。

彼女は、これら3つのチームを厳密な順序（ボックス1、ボックス2、ボックス3）としてではなく、順序は関係ないが重複は存在する「マルチセット（多重集合）」、つまり「袋」として扱います。もし、3つの同一な数字の袋を持っているならそれは一つの状態であり、2つが同一で1つが異なるなら、それはまた別の状態です。論文は、数字をラベルし直したり（リラベル）、袋を入れ替えたりしても、2つの数独バンドが「双子（等価）」であるための必要十分条件は、それらの数字チームの袋が同じであることだと証明しています。

「手計算」によるブレイクスルー

この論文の最もエキサイティングな部分は、彼女がこれらの「袋」をどのように数えるかという点です。最終的な結果を得るためにスーパーコンピュータを使って何百万もの可能性をチェックする代わりに、ペレイラはバーンサイドの補題と呼ばれる数学的定理を使用しています。この定理は、賢いカウントのショートカットのようなもので、異なる対称性を適用したときに、どれだけの要素が不変であるかを調べることで、ユニークなグループがいくつ存在するかを導き出すことができます。

この「分割の袋」のアイデアにこの定理を適用することで、彼女は閉じた解析的な公式を通じて、数字の44を導き出すことができます。彼女は問題を30種類の異なる数字シャッフルパターン（サイクル型）に分解しました。各パターンについて、どの「袋」が変化しないかを計算します。その後、19個の特定の非ゼロの計算結果を足し合わせます。最終的な和を特定の数で割ると、正確に44に到達します。

しかし、このエレガントな公式に至る道程には、計算による補助が必要でした。44のクラスを導き出すプロセス自体は、コンピュータによる列挙を必要としない閉じた形式の計算ですが、著者は数学的な議論の開発にAIツールを使用し、計算の検証を行うためにPythonスクリプトを作成したと記しています。これらのスクリプトは、カウントの分解と最終的な合計が、全置換に対する直接的な評価と一致するかどうかを独立してチェックしました。これにより、「手計算」による論理が力任せの現実（ブルートフォース）に対して成立していることが保証され、44のクラスが確かに正しい構造的結果であることが確認されました。

これは、視点の大きな転換です。論文は、44という数字が、単なる長くアドホックな簡約プロセスの乱雑な副産物であるという考えに明確に反論しています。むしろ、これら44のクラスは、対称性のルールの下で数字の分割を配置するユニークな方法を数える際の、自然な結果であることを示しています。

大きな構図

論文の主な焦点は、上部バンドの44のクラスにありますが、すべてのユニークな数独グリッドの総数についても触れています。それは、ラッセルとジャービスがコンピュータを用いて見出した、5,472,730,538という本質的に異なるグリッドの既知の数を確認するものです。ペレイラのメソッドは、単にこれを再検証するだけではありません。それは、そのより大きなカウントの基礎となる44のクラスに対して、構造的な説明を与えるものです。

要するに、この論文は、長い旅の途中のランダムな立ち寄り地点に見えた数字を、明確で美しい地図を持つ目的地へと変えたのです。彼女は、5つの複雑なトリックの連鎖を、単一のエレガントな不変量（分割のマルチセット）と、単一の強力な計算へと置き換えました。その結果は、44のクラスが計算上の偶然ではなく、数独の世界における根本的な特徴であることの証明であり、最終的な解析ステップは手計算で達成可能であり、その根底にある論理はコンピュータによって厳密に検証されているのです。