« ■Flashの格差社会 | トップページ | ■コマネチ大学数学科44講:論理学 »

2007年5月 3日 (木)

■数独の解は何通りか?

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

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

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

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

20070503_03

で、考え方としては、左上の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/

20070503_04

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

数学オリンピック2000‐2005 数学オリンピック2000‐2005

販売元:日本評論社


|

« ■Flashの格差社会 | トップページ | ■コマネチ大学数学科44講:論理学 »

コメント

こんにちは。はじめまして。戸神と申します。
ふと自分の名前で検索かけたらここに辿り着きました(笑)
とりあげて下さってありがとうございます。

大部分はB. Felgenhauer氏とF. Jarvis氏のおかげ
なのですけどね…。
論文は、些細な発見と気合いのデータ生成で
成り立っている感じです。
数独で卒業した人はまずいないのではないかと(笑)

ではでは。どうも失礼いたしました。

投稿: seiya | 2007年10月 2日 (火) 04時49分

戸神星也さま、コメントありがとうございます。

「星也」って、セイント星矢みたいで、カッコいいですね。で、卒業したあとは、何をしていらっしゃるのでしょうか。純粋に「理学部情報科学科」を出た人は、どんな職業に就くのだろう……という興味です。

投稿: Gascon | 2007年10月 2日 (火) 12時18分

返信ありがとうございます。
コメントしたことを思い出し再訪しました。

現在はなんとか社会人をやっています。
同期はほとんど進学しましたし、
こういう会社に入るケースも稀です。たぶん。
で、こんなところにいます↓
http://www.zkaiblog.com/sostaff/archive/37

>セイント星矢
よく言われます(笑)

投稿: seiya | 2007年10月12日 (金) 04時04分

2002年度の渋谷教育学園渋谷中学校の算数の入試問題に同じ問題が出ています。
入試問題の方では数字でなく四色のボールを当てはめるという内容ですが条件は一緒です。
比較的簡単な部類の問題とはいえ高校生を対象にした国際大会の問題と同じのものがでるとは、恐るべし中学入試といったところですね。

投稿: 万打無 | 2008年11月10日 (月) 14時06分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/99648/6296206

この記事へのトラックバック一覧です: ■数独の解は何通りか?:

« ■Flashの格差社会 | トップページ | ■コマネチ大学数学科44講:論理学 »