■数独の解は何通りか？

「たけしのコマネチ大学数学科」は深夜番組なので、放映時間まで、焼酎「いいちこ」を飲みながら、数学の問題を解いて、頭を数学モードにしようと試みてみるが、たいていは、番組が始まる前に酔いつぶれてしまう＞＜；

で、今回は、「数学オリンピック2000-2005」という本からの出題。

問題：4×4のマス目を作り、1から4までの数字をそれぞれ4つずつ書き込む。ただし、以下の条件を満たすものとする。
1：各行には、1,2,3,4が1回ずつあらわれる。
2：各列には、1,2,3,4が1回ずつあらわれる。
3：全体を図のように太線で4つの部分に分けたとき、各部分に1,2,3,4が1回ずつあらわれる。
このような数字の書き込み方は何通りあるか。

「数独」を一度でも遊んだことのある人なら、このルールは非常にわかりやすいものだと思う。

で、考え方としては、左上の4つのマス目には、1～4までの好きな数字を書き込めるので、4!(4の階乗：4×3×2×1)で、24通りあることがわかる。そこで、一番上の行に注目すると、たとえば、左上のマス目に「1と2」が使われていた場合は、「3か4」であり、順番をひっくり返しても2通りしかない。これは、2行目でも同じで、左の2行目が「3と4」なら、「1と2」の順列を書き込むしかないわけだ。というわけで、左上のマス目の数字が決まった状態では、右上のマス目は、2×2の4通りのパターンがある。左下のマス目も同様で、左上の数字が確定すれば、4通り。これで、右下のマス目も確定されるのだが、やはり4通りある。

つまり、答えは、4!(24通り)×(4通り×3＝12通り)で、288通り。

数学オリンピックの出題の中では、比較的、容易な問題ではないかと思う。

ところで、気になるのは、「数独」の解の盤面数のパターンは何通りあるか？ ということ。「数独」は、太線のワクが「2×2」ではなく、「3×3」のマス目が3行×3列、9個並んだもの。おのおのの太線のマス目には「1～9」の数字が入る。この問いかけに対する研究は、言われるまでもなく、研究されていて、対称性を考慮しないと、6,670,903,752,021,072,936,960通り。対称な物を同一とすると、5,472,730,538通り。……となっている。約67垓(6.7×(10＾21))通りと言われてもなー；；もしも、現在のコンピュータの性能で総当りの組み合わせパターンを求めると、およそ10＾17秒(約300年)かかるらしい。

東工大の理学部情報科学科の戸神星也(指導教官：渡辺治)氏の論文によると、ブロックごとの同型変換などのアルゴリズムの改良により、東工大のスパコンを使い4時間ですべての「数独の解」を数え上げ(インデックス化：番号付け）を行った。

下記のサイトで、「0～6670903752021072936959」のすべての解の盤面パターンの中から、任意のインデックス番号を入力すれば、「数独」の解盤面が10秒ほどで表示される。酔っ払い爺には、肝腎の工夫を凝らした数学的なアルゴリズムはわからないけれど「すげ～～～っ」の一言＾＾

■数独インデックス
http://doorgod.org/sudoku/

でも、やはり麦焼酎「いいちこ」と「数学」は、相容れないみたいで、今夜も撃沈しそう；；

数学オリンピック2000‐2005 販売元：日本評論社

---