← StudyX Devlog

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

Hiroki ObaraHiroki Obara · DeveloperSudoku365使い方
ラテン方陣とは:完成した数独もその一種になる数の並べ方

次の表は、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 の始め方 に書きました。

App Store でダウンロード Google Play で手に入れよう

Sudoku365毎日ナンプレ、2人でも