TIM Labs

2017年10月アーカイブ

9x9のナンプレのヒント数の最少は17個であることが 2012年1月1日、アイルランドの数学者Gary McGuireによって証明されている。
しかし、ヒント数16のナンプレが出来たと、先日東京青山であった、MATH POWER 2017 で発表された。

これはどういうことだろうか?
証明が間違っていたのだろか。
あるいは、発表が間違っていたのだろうか。

まずヒント数についてだが、通常の数独のヒント数(問題に最初から示される数字の個数)は17個が最少である。
その例を次に示す。
9x9-17.png
ナンプレの問題は、点対称に数字が配置されていることが多いのだが、ヒント数17では点対称の問題はまだ発見されていないらしい。この問題は、対角線に対して対象にヒントを配置したものであり、難易度はやや高いものの中級程度である。

ヒント数をもっと少なくするにはどうすれば良いだろうか。
ナンプレには、全部で27個の制約条件がある、縦9マスの数字が全て異なるというのが全ての縦列についあるので、これで9個の制約条件がある。横についても同様で、9個の制約条件がある。そして、3x3のブロック内の数字も全て異なるというので、また9個の制約条件があり、全部で27個の制約条件がある。
本当は、一部の制約条件は、他の条件から導かれるのであるが、とりあえず小さいことは無視しよう。

さて、ヒント数を少なくするにはどうすればよいだろうか。
制約条件を増やせば、ヒント数は減らせるはずである。


printfといえば、C言語のこれが有名である。

printf("hello, world\n");

というか、プログラミング言語C の本は、これで始まる。

実際にはprintfは、%何とかの形式で色々書式指定することにより、整形されたプリントのために使われる。

C言語のprintfが評価されたのであろう、このprintf が今では多数の言語に実装されている。
Wikipediaにちゃんとprintfのページがあり、英語版の方はしっかり書かれている。
programming languages with printf によると、25ほどのプログラミング言語が並んでいて圧倒される。

printf という関数あるいはメソッドは、実はプログラミング言語だけにとどまらず、シェルにも実装されている。
以下ではbashの例を示すが、他のシェルでも実装されているのではないかと思う。

まずは、基本的な使い方である。
単にメッセージを出したければ、echoを使えば良いだけなのだが、整形を色々したければ、書式指定文字列でできる。

$ greeting="Hello shell"
$ echo $greeting
Hello shell
$ printf "message:%s\n" $greeting
message:Hello
message:shell
$ printf "message:%s\n" "$greeting"
message:Hello shell

printfの出力をシェルの変数に代入して後て使いたいときがある。
そのときは、次のように、printf全体を$()で囲むとできる。

$ text=$(printf "message:%s\n" "$greeting")
$ echo $text
message:Hello shell

10進数、16進数の変換も可能である。

$ v=1000
$ printf "%x\n" $v
3e8
$ printf "%#x\n" $v
0x3e8
シェル上で浮動小数点数の演算も行いたい場合には、 bc(An arbitrary precision calculator language)を使えば可能であるが、そこまでの偏執狂者ではないのでシェル上では浮動小数点は扱わないことにしている。 そういう場合は、何らかのスクリプト言語を使う。
でも、どうしても全てをシェルで書かないと気がすまないシェル教徒を制止する気はない。
MATH POWERも、開始24時間を過ぎ、じわじわと埋まってくるのだが、よく見るとこんなミスが発生しているのだ。

DSCN0890 (600x448).jpg
D1の上の9x9(青枠)は埋まっているのだが、その右の9x9の青枠の中で矛盾が発生している。
重なっているオレンジ枠の最上段が、6 2 5 9 _ 31 _ _ となっているのだが、この1の右マスには入れられる数字がないのだ。
つまり、どこかが間違っている。

答の同じ部分:
anspart1.png
D1の上の9x9の中にミスがかなりある。
ということで、親切に間違っているところをどんどん消すことで応援することにした。

実は、これをやると忙しい。
どこに発生するかわからないので、答を持っているからといって、全マスチェックするのは大変だ。
最終的にどこまで(何合体)完成したかの確認のために、チェッカーが2名いる。
だから、チェッカーというより、ミスに陥って、ミスが蔓延するのを適当に防ぐ必要があるので、効率よくチェックすることにした。

10月7日、8日に東京青山のスパイラルホールで32時間連続のイベント「数学の祭典 MATH POWER 2017」が開催された。
イベント全体の内容は、以下のページで見られる。
MATH POWER 2017 のイベントを一気に35時間見たければ、ニコニコ動画で見られる。

mathpower2017.pngのサムネール画像   

多数の来場者で解かれた247合体の問題は、MATH POWER 2017 の公式ページにて公開中。


さて、247合体は、ホールに入る前のホワイエの、受付の裏側に、横6m、高さ1.5mで貼られていた。 表面はホワイトボード状になっていて、細字のマーカーで書き込む。
開場直前の写真である。
どうして照明が不足するので、上にライトを並べてある。


247GATTAI.JPG
MATH POWER 2017が近づいてきた。
参加される方は注意:場所が、六本木のニコファーレから、青山のスパイラルホールに変更になった。
詳しくは、以下で確認を。

mathpower2017.pngのサムネール画像


さて、「もっと社会に数学を」ということで、今回は巨大合体ナンプレではなく、数学の、それも思いっきり飛んだ数学の本を紹介しよう。

パリコレで数学を (419x600).jpg
パリコレで数学を
les mathématiques au défilés de mode

サーストンとポアンカレ予想

著者   阿原一志
ISBN   978-4535788145
判型   A5
ページ数 186
発行   日本評論社
発行日  2017/8/25

サポートページ





ISSAY MIYAKEのパリコレに数学を取り入れよう。
それも、超難解で有名なポアンカレ予想を元にしたイメージでデザインしようということになり、数学的な説明をするにはこの先生が適切と推薦されたのが著者の阿原氏である。
氏は、最近話題の明治大学総合理工学部(中野キャンパス)先端メディアサイエンス学科・FMSの教授である。
本書は、著者がISSAY MIYAKEのクリエイティブディレクターの藤原大氏への対話の形式である。

副題にもある「ポアンカレ予想」についてはまったく詳しくないので、そのあたりの説明は無視して読んだが、それでも読み進めばなんとなく「絡み目」について分かってくる。

本を開くと、カラーのファッションショーの写真が続き、その後に本書で延々と説明がある「絡み目」、要するに紐などの写真がある。
この写真を見たとき、著者はパリで指導したのかと思ったら、日本で教えただけらしい。

最初に、サーストン教授から渡された「8つの宇宙の形」という絡み目の絵が出てくる。
この8つの絡み図は、幾何化予想に対応しているのだが、詳しいことは説明できないので、自分で調べて欲しい。
絵は紐が絡まっている図なのだが、それが宇宙とどう関係しているか、幾何学と関係しているかの説明が延々と続いて1冊の本になっている。

トポロジーの世界なので、図がどんどん変形していく。
面を曲げて貼り付けたり、伸ばしたりするのであるが、複雑になってくると想像がしだいに困難になり、頭が絡んでしまう。
目で追っていくだけで、結局は同じ絡み目であることが分かることもあるが、困難なものは実際に紐で同じものを作り、ごちゃごちゃ弄り回すと、あるとき突然同じになって、同じこと(同相)は分かったが、変形手順は謎のままで終ることが多かった。

本書には、数式がほとんどない。
それでも、数式レベルのことも知りたい読者のために、各章の最後に宿題がり、計算問題が入っている。

本書は、どういう人が読むのであろうか?
位相数学をちゃん勉強する人は、他書を読むと思う。
それより、数学と社会、デザインの関係などをぼんやりと理解する、イメージするための本であろうか。
数式なんてもう何年、何十年も書いていないような人でも、最先端の数学の一端に触れることができる本と言えば良いだろうか。
MATH POWER 2017で挑戦してもらう247合体ナンプレ関連についてあれこれ書いてきたが、もうイベントの日が間近だ。
ということで、合体ナンプレでしか経験できないような事を紹介しよう。

次の図の状態まで解き進んだとしよう。
まだ決まるところは色々あるのだが、非常に特徴的な決まり方がある。
それも、連続技といか、芋づる式というか、どんどん決まるのがある。

どんどん決まるのは、9x9の普通のナンプレでもあるのだが、この問題では、ある数字について、かなり広範囲に決まっていくので、次を見る前に、ぜひ自力で見つけてみよう。

candidate4 (700x686).jpg何が芋づる式かを以下に示す。

合体ナンプレを解くとき、マスに入れる数字が1つに決まる場合は良い。
しかし、そういう場合は少なくて、いくつかの数字が入る可能性があるのが普通だ。
マスに入る可能性が残っている数字のことを「候補」という。
何の制約もないとき、マスには1から9までの9個の候補がある(最大)。
しかし、注目しているマスが入っている行、列、ブロックにある数字は、そのマスに入れることができないので、候補から消す。
すると、数個の候補が残る。

candidate1.png しかし、これでも大変だ。

最初に、全ての空きマス(未決定マス)に候補を全部書き込んでいる人を見かける。
9x9のナンプレでも、もし50マス空きがあり、平均4個候補を書こうとすると、200個も数字を書かないといけない。
それに、多数の小さな数字を書き加えると、盤面が非常のごちゃごちゃしてしまう。

そういうこともあって、ナンプレに慣れている人は、少しの候補だけを効率よく書き加えては考えるのが普通だ。
たとえば、こんな感じに書き加える。

candidate2a (600x587).jpgある数字の候補を入れられるマスが9マスよりなる同じ縦列、横列、ブロック内に2マスだけになった場合に書き込むことが多い。
さらに、その2マスが縦か横に2マス連続している場合、2マスの中央(境界線上)に書くことが多い。、

青の丸数字は、初期状態で決まる数字であり、丸の無い青色は、問題およびその後に決まった数字の影響で確定したもの。
そして、小さい紫色の数字が候補である。

上の途中図は、適当な解きかけの状態である。
候補まで考えなくても、まだまだ決められる箇所はあるのだが、全部きちんと調べるのは人間には難しい(コンピュータにはやさしい)。

さて、上の図の状態で、候補同士の影響で決まる箇所がある。

このアーカイブについて

このページには、2017年10月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2017年9月です。

次のアーカイブは2017年11月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。