ラテン方陣とは:完成した数独もその一種になる数の並べ方

次の表は、1、2、3の3つの数字を、どの行にもどの列にも1回ずつ並べたものです。
1 2 3
2 3 1
3 1 2
このような表を「ラテン方陣」と呼びます。英語版 Wikipedia の Latin square の定義では、n×n の表に n 種類の記号を入れ、どの記号もそれぞれの行にちょうど1回、それぞれの列にちょうど1回あらわれるものです。日本語版 Wikipedia では「ラテン方格」という名前で載っています。上の表は、大きさ3のラテン方陣です。
完成した数独の盤面も、ラテン方陣の一種です。英語版 Wikipedia の Latin square には、数独の答えはどれもラテン方陣だと書かれています。数独とナンプレの違い、名前の由来 と 数独の答えの盤面は何通りあるか でも少しだけ触れました。この記事では、ラテン方陣そのものを見ていきます。
名前の由来
「ラテン方陣」という名前は、18世紀の数学者レオンハルト・オイラーの論文に由来します。オイラーは、表に入れる記号にラテン文字(ローマ字)を使いました。英語版、日本語版の Wikipedia のどちらにも、この由来が書かれています。
記号は、数字でも文字でも色でもかまいません。最初の表の1をA、2をB、3をCに置きかえると、次のようになります。
A B C
B C A
C A B
どの行にもどの列にも、A、B、Cが1回ずつ入っています。これも同じラテン方陣です。
小さなラテン方陣はいくつあるか
大きさが2なら、ラテン方陣は2通りしかありません。
1 2 2 1
2 1 1 2
大きさが大きくなると、数は急に増えます。英語版 Wikipedia の Latin square には、大きさごとの個数の表があります。そのうち5までを抜き出すと、次のとおりです。
| 大きさ | すべてのラテン方陣 | 標準形 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 12 | 1 |
| 4 | 576 | 4 |
| 5 | 161,280 | 56 |
「標準形」は、1行目と1列目が1、2、3…の順に並んでいるものです。どのラテン方陣も、行や列を入れかえれば標準形にできます。大きさ3の標準形は、最初に挙げた表の1つだけです。
同じ表では、大きさ9のラテン方陣は 5,524,751,496,156,892,842,531,225,600 通りです。完成した数独の盤面は 6,670,903,752,021,072,936,960 通りです。
数独とラテン方陣の違い
ラテン方陣が求めるのは、行と列に同じ記号がないことだけです。数独は、そこに3×3のブロックの条件を加えます。
小さな4×4で比べてみます。4×4の数独は、1から4を使い、行と列と2×2のブロックに同じ数字が入らないようにするものです。
1 2 | 3 4
2 1 | 4 3
3 4 | 1 2
4 3 | 2 1
この表は、どの行にもどの列にも1から4が1回ずつ入っているので、ラテン方陣です。けれども左上の2×2のブロックには、1と2が2回ずつ入っています。数独の答えにはなりません。
2行目と3行目を入れかえると、次のようになります。
1 2 | 3 4
3 4 | 1 2
2 1 | 4 3
4 3 | 2 1
今度は、4つのブロックのどれにも1から4が1回ずつ入っています。ラテン方陣で、しかも4×4の数独の答えです。
大きさ4のラテン方陣は576通りあります。4×4の数独の完成盤面は、数列の辞典 OEIS の A107739 によると288通りです。大きさ4では、ちょうど半分のラテン方陣が数独の答えになります。
1700年の崔錫鼎と、オイラー
ラテン方陣の例を最初に発表したのは、朝鮮の数学者、崔錫鼎(최석정)です。英語版 Wikipedia の Latin square によると、1700年に大きさ9のラテン方陣の例を発表しています。オイラーより67年早いことになります。
ラテン方陣の一般的な理論を始めたのは、オイラーです。オイラーは1782年に「新しい種類の魔方陣についての研究」と題した論文を発表しました。オイラーの著作を集めた Euler Archive の E530 に書誌がまとめられています。
36人の士官の問題
この論文で扱われているのが、「36人の士官の問題」と呼ばれる問いです。英語版 Wikipedia の Mutually orthogonal Latin squares が引くオイラーの言葉では、6つの連隊から集めた36人の士官を正方形に並べ、縦のどの列にも横のどの列にも、階級も連隊も違う6人がいるようにする、という問題です。
連隊で1つのラテン方陣、階級でもう1つのラテン方陣を作り、2つを重ねたときに、連隊と階級の組み合わせが1つも重ならないようにする、ということです。このように重ねられる2つのラテン方陣を「直交する」と呼びます。
大きさ3なら、次のように作れます。
1 2 3 A B C 1A 2B 3C
2 3 1 + C A B = 2C 3A 1B
3 1 2 B C A 3B 1C 2A
右の表には、1から3とAからCの組み合わせ9通りが、1回ずつ入っています。オイラーは、ひとつのラテン方陣にラテン文字を、もうひとつにギリシャ文字を使いました。そのため、こうした組を「グレコ・ラテン方陣」とも呼びます。
36人の士官の問題は、大きさ6のグレコ・ラテン方陣を作れるか、という問いになります。オイラーは、大きさ6を含め、4で割って2余る大きさでは作れないと予想しました。Euler Archive の解説では、この論文でオイラーはたくさんの例を示しつつ、厳密な証明なしにそう論じています。
大きさ6で作れないことは、1901年にガストン・タリー(Gaston Tarry)が、すべての場合を調べ上げる方法で確かめました。一方で、大きさ7以上についてはオイラーの予想は誤りで、グレコ・ラテン方陣は大きさ2と6を除くすべての大きさで作れることが、のちに示されています(Mutually orthogonal Latin squares)。
実験計画で使われるラテン方陣
ラテン方陣は、パズルの外でも使われています。英語版 Wikipedia の Latin square によると、農学の研究の実験計画に使われ、実験の誤差を小さくするために使われています。互いに直交するラテン方陣の組は、誤り訂正符号にも使われています。
数独の3つ目の条件
ラテン方陣の2つの条件に、ブロックという3つ目の条件を加えると数独になります。大きさ9の完成盤面は、それでも66垓通り以上あります。数独のルールそのものは ナンプレのルール:はじめての人が知っておくこと に、ブロック以外の条件を足した仲間のパズルは ナンプレの種類:対角線・ジグソー・キラーなど に書きました。
Sudoku365 について
Sudoku365 は、iPhone、iPad、Android で遊べる数独のアプリです。盤は標準の 9×9 です。「かんたん」「ふつう」「むずかしい」「エキスパート」の四つの難易度に 300 問ずつ、計 1200 問が入っています。毎日一問のデイリーチャレンジと連続記録があり、Bluetooth で2人で対戦や協力をすることもできます。
ゲーム画面の「メモ」をオンにすると、マスに候補を書けます。設定の「メモから数字を消す」(初期はオン)にしておくと、正しい数字を置いたときに、関係するマスの同じメモが自動で消えます。マスを選ぶと、同じ行・列・ブロックと、同じ数字のマスがハイライトされます。
アプリは無料で、広告が入ります。「広告を削除」の買い切り(1,500円)で広告を消せます。ひとりで毎日続けるための使い方は Sudoku365 活用のヒント に、最初の一問の始め方は Sudoku365 の始め方 に書きました。
Sudoku365毎日ナンプレ、2人でもアプリを見る →