読者です 読者をやめる 読者になる 読者になる

愛とは、全人生をかけてアイドルにチェスを教えること。

フリルドスクエアと行く、奥深いチェスの旅。

一ノ瀬志希のブレイクタイム[Knight's Tour / Eight Queen]

 

 ん~おはよう、一ノ瀬志希だよ♪

f:id:rikkaranko:20170327190522j:plain

 最近みんな頑張ってるよね~ちょーっと真面目な感じが続いてるから、この志希ちゃんがガス抜きをして進ぜよう~♪

 

 今日あたしがキミに紹介するのは、チェスボードとピースをいくつか使った遊びだよ~。

  • Knight's Tour

 まずこれ。『チェスボード上のナイトを移動させ、全てのマスを一度ずつ移動させる』っていうパズルだよ~。数理パズルとしては比較的、ゆーめいだね。ナイト・ツアーなんて呼ばれてるよ。

 

 最初はシンプルなナイト・ツアー。8×8の普通のチェスボードで考えてみようか~!

f:id:rikkaranko:20170327213922p:plain

 ん~、じゃあ白の右のナイトの初期位置を出発点(1)にしよう!

f:id:rikkaranko:20170327214049p:plain

 で、ここからナイトの利きを使っていけるマスは3種類!っていう感じで、チェスボード全部のマスを通ることはできるでしょーか!っていう問題だよ~。ん~?数学じゃんって?そうだよ!

 あたしはカガクシャ、ケミストの方だけど、自然科学の共通言語は数学だからね!一定以上の科学者に数学の力は必須だよん。

 

 こーいう問題をどう考えるかにゃ。というときに、人間は結果から逆算できるから便利だよね!

 全部埋まった状態、っていうのを仮定するんだよ。すると、それは(64)のマスで、一意に決まる(63)のマスからトリップしてきたに決まってるじゃんね~。ということは、(63)だって(62)のマスから一意にトリップしてきた訳で……?おっと、ひとつ解が浮かんだぞな。

 つまり、こーいうルールを導入してあげればいいんだよ!

  1. ナイトは到達可能なマスの候補のうち、「そのマスから到達可能なマスの数が最小」となるようなマスに進む
  2. 1.を満たすマスが複数ある場合はどちらに進んでもよいとする

 これでいいね。ちなみに、このルールはWarnsdorf's Ruleという名前で呼ばれているものを超簡潔に書き直したものだよー。

 このルールに従って埋めてみれば、一例はこ~んな感じ?

f:id:rikkaranko:20170327214948p:plain

 これは「一筆書き」なんかととても縁の深い問題だよね!スタート位置を変えてみても巡回できるのか、とか、スタートとゴールが一致できるか、とか、8×8に拘らず、n×nにしてみたら……とかさ!ちなみにn=1,2,3,4のときはそのような経路は存在しません。しかしその証明を書くには余白が狭すぎる……

 

 数学パズル、ってさっき言ったけど、この問題は立派なひとつの数学の分野の問題だよ。こーいうのを研究するのが、グラフ理論ってやつだね!グラフっていうと、ハイスクールでやるような、関数のグラフが思い浮かぶかな?でもここでいうグラフはそーゆーのじゃなくて、単に「ノードとエッジで構成されるグラフ」だよ。噛み砕くと、そうだね、頂点と線からなる幾何模様だよ!

 

 そんなものを扱う学問がどんなことに役立つのかって?たとえば、「四色問題」というのは聞いたことあるでしょ。今は証明が与えられたから「四色定理」と呼ばれているけれどね~。「平面上のいかなる地図も、隣り合う領域が異なる色で塗られる様に塗り分けるには高々4色あれば十分」ってやつだ!

f:id:rikkaranko:20170327220316j:plain

 こんな地図を考えてみると、これ実は、次のグラフを考えて、隣り合う頂点が異なる色になる様に色を塗る問題にすり替えることが出来るんだよ!すりかえておいたのさ!

f:id:rikkaranko:20170327220841j:plain

 こういうことだね!

f:id:rikkaranko:20170327221035j:plain

 こうやって、考えている物事を捨象して簡単な問題に置き換える!そういう学問だよ。

 

 グラフ理論では、グラフのすべてのノードを1度ずつ通るような経路を「ハミルトン路」と呼ぶんだよ~。ふっふ~、つまり、ナイツ・ツアーはハミルトン路が存在するかどうか、という問題だったんだよ♪始点と終点が一致するようなハミルトン路が存在するようなグラフはハミルトングラフ、と呼ぶんだ。チェスボードはハミルトングラフだね!

 ということは、ナイツ・ツアーには、全部のマスを通って元の位置に戻ってくるような経路があるって意味だよ!やってみてね~

 

 なんであたしがハミルトン路を導入したかってことだね。スーガクシャとかって、わざわざ難しい物言いをしたりするイメージない?ある?やっぱあるよね、にゃはは。これは誤解だよ!マトモな数学者は問題を簡略化することはあっても、簡単な問題を複雑化させることはないからね。ここでゆーところの複雑化っていうのは、一般化とは別の概念!例えば、8×8のチェス盤から9×9の将棋盤に代えてナイツ・ツアーを試みる……っていうのは、一般化の実験だよ。あたしがここで想定している複雑化というのは、床に落ちたコインを拾うために、超強力な電磁石を開発する……みたいなことだよ!

 

 つまり、あたしはこれからハミルトン路という概念を導入することである問題を簡略化しようとしているんだよ~。

 それは、n×n(nは自然数ね)のチェス盤でナイツ・ツアーを考えた場合、全てのマスを通る経路は存在するか、という問題。さっき言ったように、n=1,2,3,4のときは存在しないね。それで、n=8のときは存在することをあたしたちは知っている。

 まず、実験実験~。n=5のときはどうかな?Warnsdorf's Ruleを用いてあげれば、こんな感じ!

f:id:rikkaranko:20170327222528p:plain

 という感じで、n=6,7,8,9についてまずハミルトン路が存在することを示せる。

 次に、5×5を幾つか横並びにつないだグラフはかならずハミルトン路を持つことも証明できる。

 そうすれば、10以上のn×nについては、(n-5)×(n-5)と、5×5と、5×(n-5)のグラフの組み合わせだから、ハミルトン路が存在することが証明できるよね~。つまり、nが5以上の整数のとき、n×nでもナイツ・ツアーが可能な経路は存在する、ってことだね。 

 

 今度のは、エイト・クイーンと呼ばれるプロブレムだよ~。

 『8×8のチェスボード上に、8個のクイーンを、お互いがどの別のクイーンにも取られないように配置することはできるか』、というのが問題!みんなも挑戦してみてね。ふっふ~、あたしはいくつか見つけたよ~。たとえばこんな感じだね!

f:id:rikkaranko:20170327223528j:plain

 この問題も一般化ができるよね~。さしずめ、N-クイーン問題、とでも呼ぼうか~。

 『n×nのチェスボード上に、n個のクイーンを、お互いがどの別のクイーンにも取られないように配置することはできるか』さぁ、どうかな~。できるなら、すべての場合を答えなさい、なんて付け加えてもいいよね!

 n=2,3のときは明らかに無理だよね。いいヒマつぶしになるよ~、あたしは飽きちゃったけどね!n=8だと基本解は12パターンだね!あとは回転や鏡像の配置を別物とカウントするなら、全部で92パターンになるよ。

 

 実はこの問題、さっきのナイツ・ツアーと違って、まだ解かれていないんだ。なんでかっていうと、これはグラフ理論の問題ではなくて、組合せ論に属する問題だからなんだよね。で、得てして組合せ論は人間が論理だけで追いかけて解けるようなレベルじゃない問題が最近多くてさ。コンピュータ様のお力を借りて計算量でブン殴っちゃう♪みたいな解き方が、きっと世界のどこかで今も行われているのでしょう~。もっとも、グラフ理論の問題でも、人間には太刀打ちできないくらいの計算量を要求するものもゴロゴロあるからね。四色定理もコンピュータ様が解いたんだよ!ただ、組合せ論はその傾向が大きいってだけのハナシ。組合せ爆発、っていうんだけどね。

 

 ちなみに、いま解が出ている最大のnは、ドレスデン工科大のグループが2009年に求めたn=26の場合だよ。ドレスデン工科大は昔、ウチのプロデューサーが研究してたところだったかなー。偶然ってあるんだね!

 

 なんであたしがこういうこと紹介したくなったのかっていうとね、ファインマンって偉い物理学者がこう言ったんだ。

――数学や物理というのは神様のやっているチェスを横から眺めて、そこにどんなルールがあるのか、どんな美しい法則があるのか、探していくことだ。

ってね。なかなか、シゲキテキな言葉でしょ?それだけチェスというのは美しい、という賛美にも聞こえるし、はたまたチェスとは神様が人間に与え給うた人類の至宝とも聞こえるし。

 チェスって大変キョーミ深いよね!まだまだ、あたしの知らない世界があの盤上には広がっている気がしてるんだ!じゃあね!

 

(続く)