数独の数学について詳しく解説

導入

古典的な数独グリッド

正方形間の比較に基づいた Sudoku のバリエーション

対角線に追加の制約を加えた古典的な数独

Sudoku ゲームは、 N個の正方形のN個の領域に分割された正方形のグリッドを完成させることで構成されており、各行、各列、各領域に 1 からNまでの数字が 1 回だけ現れるように、部分的に数字が埋め込まれています。

Sudoku の数学的分析により、このゲームとそのバリエーションの背後に隠されたさまざまな特性と問題を発見することができます。

導入

Sudoku の数学的分析は、完全なグリッドのプロパティの分析とグリッドの解像度の分析という 2 つの主要な部分に分かれています。

グリッド分析は、ゲームのさまざまなバリエーションに対して考えられる解決策を列挙することに主に焦点を当てており、解像度の研究では、初期のグリッド値と完全なグリッドに至るまでのステップに焦点を当てています。これらの技術には、組み合わせ分析、アルゴリズム、群理論、およびコンピューターによってグリッドを迅速に解決できるため、プログラミングなどのいくつかの分野が必要です。

Sudoku には多数のバリエーションがあり、一般にグリッドのサイズ (パラメーターN ) と領域の形状によって特徴付けられます。古典的な Sudoku のNは 9 で、領域は 3×3 の正方形です。長方形の数独には、 L × C のサイズの長方形領域があります。ここで、 Lは行数、 C は列数です。 L × 1 (または 1 × C ) のサイズを持つこのような数独は、領域が単一の行または列であるため、ラテン方陣になります。

追加の制約(サムナムピュアまたはキラー数独、ココノツによる対角の一意性の尊重、 Greater -Thanによる要素の順序の制約) または複数のグリッドのアセンブリ (サムライ、3D の数独)。いくつかのバリエーションでは、数字が文字に置き換えられます。ただし、ルールが同じであれば、使用する文字をこのように置き換えても、パズルの本質的な特性は変わりません。

数独の数学的分析は、ゲームの人気に伴って行われ、ゲームのアルゴリズムの複雑さと NP 完全な性質に関する分析が2002年末頃に文書化され、列挙結果が 2005 年半ば頃に現れました。多くの研究者やアマチュアの貢献により、数独のバリアントの登場により、ゲームのプロパティを更新できるようになり、考慮および探索する数学的要素がさらに拡張されました。

冒頭で挙げた 2 つの主要な数学的アプローチとは対照的に、数学的論理に基づいてパズルを解く問題に取り組むアプローチが、最近、ドゥニ・ベルティエの著書「隠れた数独の隠れた論理」で提案されました。これにより、ゲームの一般化された対称性をすべて発見して形式化し、それらに基づいて、隠れた xy チェーンなどの新しい解法ルールを発見することが可能になりました。

可能な完全なグリッドの数

可能な完全なグリッドの数は9 未満です。これは^、行と列の制約を考慮せずに領域を構築する方法の数に相当します。

2005 年に、バートラム フェルゲンハウアーとフレイザー ジャービスは、このグリッドの数が次のとおりであることを証明しました。

6 670 903 752 021 072 936 960≈6.67.10 ²¹ (詳細については、OEIS の( en ) [4] および継続 A107739 を参照)。

この数値は次と等しくなります。

9!×72 ² ×2 ⁷ ×27 704 267 971

最後の因数は素数です。この結果は徹底的な研究によって証明されました。その後、フレイザー・ジャービスは詳細な分析を通じて証明を大幅に簡素化しました。このデモンストレーションはEd Russell によって独立して検証されました。 Jarvis と Russell は後に、対称性を考慮すると、5,472,730,538 個の解が存在することを示しました [5] (詳細については、[6] および次の OEIS A109741を参照)。

一方、スーパー数独（16 × 16 マス）の完全なマス数については、現在に至るまで研究結果がありません。利用可能な問題の数を見ると、同じグリッド内の数値を明らかにする方法がいくつかあるため、この数値は大幅に大きくなります。

解像度を固有にするために事前に塗りつぶされたボックスの数を知る必要があるという問題は、今日まで解決されていません。日本人が得た最良の結果は、対称性の制約なしで 17 個の正方形でした。 [7] [8]。これより少ない数ではできないということはありません。 Gordon Royle は、次の操作を組み合わせて 2 つの解像度を相互に変換できない (またはその逆) 場合、それらの解像度は異なるものとみなされます。

1. 9 つの数字の順列
2. 行と列の交換 (転置)
3. 単一ブロック内の行の並べ替え
4. 単一ブロック内の列を交換する
5. ブロックの行上のブロックの並べ替え
6. ブロックの列上のブロックの並べ替え

線形代数における行列演算との類似性に気づきました。

用語

パズルは、初期値を含む不完全なグリッドです。リージョンはブロックまたはゾーンとも呼ばれます。混乱を避けるために、正方形という用語は避けられています。

ストリップは、水平軸上の一連の隣接するブロックです。スタックは、垂直軸上の一連の隣接するブロックです。 9×9 の正方形の Sudoku には、3 つのストリップと 3 つの山があります。

正しく設計された Sudoku には、唯一の解決策があります。つまり、最終的なグリッドは一意ですが、部分的なグリッドからの解決策は異なるパスを取ることができます。

さまざまなバリエーションの形式化

領域は、その次元L x Cで表すことができます。ここで、 Lは領域内の行数、 C は列数です。 Sudoku のクラシック バージョンでは、L = C = 3 です。これは、ストリップごとにL 個の領域があり、スタックごとにC個の領域があることを意味します。 2×6 領域には 3×4 領域と同じ数の正方形があるため、要素の数よりも領域のサイズについて言及する方が便利です。

亜種を大まかに分類するには、次の内訳を採用できます。

• 長方形領域
  • 正方形の領域
• 不規則な領域 (ポリオミノ)

追加の制約により、ゲームの種類をより適切にターゲットにすることが可能になります。

N x N領域の正方形の Sudoku には、重複がないという古典的なルールに加えて、そのすべてのサブ要素に対して尊重されるいくつかの特性があります。実際、各行と各列にはN 個の領域との交差があり、 N 個のボックスをそれぞれの領域と共有します。ストリップとスタックの数もNに等しくなります。長方形の数独にはこれらの特性がありません。

3×3 領域を持つ Sudoku は、それ自体の別のプロパティを隠します。Nはゲーム内で考慮されるサブユニットの数、つまり行、列、領域の 3 つです。

定義

どちらか ：

• 特定の次元を持ち、元の数独のルールを満たす (行、列、領域に重複がない) 数独ソリューション
• S = {s}、すべての可能な解のセット
• |S|、集合Sのカーディナリティ(サイズ) (つまり、解の数)

解の数は、グリッドのサイズ、適用されるルール、および個別の解の正確な定義によって異なります。 3×3 の領域を持つ Sudoku の場合、グリッドの内容を表示するための規則は次のとおりです。ストリップには上から下にラベルが付けられ、スタックには左から右にラベルが付けられます。したがって、領域には左から右、上から下の順に番号が付けられます。この規則は長方形グリッドにも適用されます。

3×3 領域を持つ Sudoku の場合は、他の用語も役に立ちます。

• トリプルは、領域の行または列に存在する 3 つの値の順序なしの組み合わせです。たとえば、トリプル {3, 5, 7} は、値 3、5、7 が領域の行または列に現れるが、出現順序は指定されないことを意味します (行に 5、7 を含めることもできます)。 、3、または 3、7、5 の列でも)。トリプルの値は、順列を使用して 6 つの異なる方法 (3!) で配置できます。慣例により、トリプルの要素は昇順で書き込まれますが、これはそれらが同じ順序でグリッドに表示されることを意味するものではありません。
  • 表記 h RL は、領域Rとグリッド線Lのトリプルを示します。接頭辞h は、それが水平トリプルであることを示します。
  • 同様に、v RC表記は、グリッドの領域Rと列Cのトリプルを識別します。接頭辞v は、それが垂直トリプルであることを示します。

たとえば、h56 表記は、領域 5、行 6 のトリプルに対応します。英語では、行にはr 、列にはc という表記を使用します。

グリッドの行または列の領域に存在する部分を指定するために、ミニ行またはミニ列とも呼ばれます。