組み合わせ爆発のはなし

YouTube 上に公開された
「『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!」
という動画が話題になっている。

http://youtube.com/watch?v=Q4gTV4r0zRs

下の図のようなNxNの格子を用意して、左上のスタート地点から、右下のゴール地点にたどり着くルートの数を数えてみよう、というもの。

この例は3x3の格子。
さて、何通りあるか? ルートは最短ルートである必要はなくて、下から上に向かっても構わない。ただし、ルートは自分自身に交わってはいけない。
3x3の格子の例では、答えは184通りある。
意外とたくさんあることに驚かされる。
では、4x4の場合は?
動画の中では「おねえさん」が手で数えているけど、答えは8,512通り
5x5の場合は、もはや手で数えるわけにはいかなくなる。動画の中のコンピュータを使って求めた答えは1,262,816通り
組み合わせ爆発によって、あっというまに場合の数が増えてしまうことがわかる。

動画の中で紹介されていたのは、次の10x10まで。
最後の数字は、動画の中のスーパーコンピューターが25万年かけて導き出した答えだ。

1 2
2 12
3 184
4 8,512
5 1,262,816
6 575,780,564
7 789,360,053,252
8 3,266,598,486,981,642
9 41,044,208,702,632,496,804
10 1,568,758,030,464,750,013,214,100

もはや桁数が多くて、数としての実感がわかない。

さて、この問題は「Self-Avoiding Walk」として知られている問題で、現在は次のように19x19までの解が知られている。

1 2
2 12
3 184
4 8512
5 1262816
6 575780564
7 789360053252
8 3266598486981642
9 41044208702632496804
10 1568758030464750013214100
11 182413291514248049241470885236
12 64528039343270018963357185158482118
13 69450664761521361664274701548907358996488
14 227449714676812739631826459327989863387613323440
15 2266745568862672746374567396713098934866324885408319028
16 68745445609149931587631563132489232824587945968099457285419306
17 63448146112379639713102975407955244004494439868664806936463693
87855336
18 17821128408420651298933849466523252751678380657047676559314524
74605826692782532
19 15233449717048799930807428103192296908994542553232945557760298
66737355060592877569255844

Wikipediaによると不可思議は10^{64}なので、1不可思議を超えるのは70桁を持つ17x17以降ということになる。

奇遇にも、現在求まっている最大の19x19は、ちょうど囲碁の盤面と同じサイズだ。
身近に囲碁盤があれば、ちょっと取り出して眺めてみるといいかもしれない。問題は単純で、可能な経路はすべて1つの囲碁盤に収まるのに、左上のカドから右下のカドまで移動する方法は、ほぼ限りなく存在する。

ちなみに、あの偉大なドナルド・クヌース先生もこの問題に興味を持ち、1995年にN=12のときの解を求めている。

もしも20x20の解を求めることができたら、あなたも歴史に名前を残せるはず。

参考
・Self-Avoiding Walk | Wolfram Math World
http://mathworld.wolfram.com/Self-AvoidingWalk.html

・A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid. | OEIS
http://oeis.org/A007764


関連エントリ
数列の百科事典 OEIS | 大人になってからの再学習
無量大数とグラハム数 | 大人になってからの再学習

数え上げ数学 (すうがくぶっくす)

数え上げ数学 (すうがくぶっくす)