Computer

パズル問題自動生成時代 -- 概論

コンピュータの進歩に貢献

最初は数のパズル

3.14159265358979323846264338327950288419716939937510...

コンピュータは、その誕生の初期から、性能を判定する方法を常に探し求めていた。当初は、円周率の計算を競っていた。今も延々と計算桁数を伸ばしており、 2002年には東京大学で1兆桁を超える計算を行なったそうである。

円周率の計算はどこまでも桁数を伸ばすことができるだろうが、結局は非常に限られた処理を高速にくり返しているだけではないだろうか。一種の高性能は調べられるであろうが、様々な展開が考えにくい。

私も、マイコンを入手した頃、色々な円周率の近似方法を知り、実際にプログラムを組んで楽しんだ。１万桁位は一瞬で計算できたのだが、実はきちんと検算はしなかった。確かに、高精度計算の方法は身についたが、通常そこまで高精度が要求されることはないし、円周率だけでは十分に楽しむことは私にはできなかった。たいていの人は、１つの通過点として楽しんだ程度で終ったと思う。

3n+1問題

数の問題に関しては、整数論の中にいっぱい転がっている。分かりやすい問題として有名な、 3n+1問題(コラッツの問題)を取りあげてみよう。

正整数Nに対して、

  Nが奇数ならば、Nを３倍し、１を加えたものを新たなNとする。

  Nが偶数ならば、Nを２で割ったものを新たなNとする。

この操作をくり返すと、有限回でNは１に到達する。

どんな自然数Nで始めても、最終的にはNは１になるという命題であるが、まだ誰も証明できていない。また、そうならない反例も示されていない。

例： 7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1

この程度の計算なら初期のコンピュータでも十分に可能であった。実際に、パズラーでありコンピュータ技術者でもあった人々がこの問題に取組んだが、今もって反例は見つかっていない。

当初は、こういう数を直接扱うパズルに対してコンピュータを使っていた。

箱入り娘

４種類のサイズのコマ(1x1,2x1,1x2,2x2)を空きマスを利用して動かして、 2x2の娘コマを下の出口まで、できるだけ少ない手数で移動するパズルである。一度に動かせるのは１つのコマで、上下左右に続けて何マスでも移動できる。

このパズルは、数字ではなく、コマの移動を行なうもので、元々はフランスで「赤いロバ」と言われていたものが日本に入ってきたものらしい。

このように、コマをスライドさせるパズルを一般にスライディングパズルと言うが、何手で解けるのかを調べるのはなかなか大変だ。人間がやろうとすると、何等かの記録をしなければいけないので、非常に骨が折れる。

それでも、大変な人気が戦前に出たようで、83手が最小手数として知られていた。まあ、このくらい手数が長くなると、全部の可能性をきちんと調べるというのは、とても人間のできることではなくなる。

そのうち、コンピュータの能力も上がり、大企業や大学の大型コンピュータをパズルに使ってしまう不届き者が出て、今までほとんど数値計算しかやらせていないコンピュータに対して、より複雑な処理を試みた。

箱入娘の場合には、盤面の状態を何とか数字で表現しようとして苦労した。そのおかげで、パズルの盤面の状態をコンピュータ上で表現することに成功し、箱入り娘の最小手数も求まった。８３手ではなく、８１手と分かり、手順も同時に示された。

もっと様々な問題について知りたい場合には、スライドパズル問題集が参考になろう。

さて、このパズルだが、短い手数の場合は力づくで解いても大丈夫だ。今のコンピュータなら、箱入娘くらいなら楽勝だろう。学部学生向け演習問題として適当だろうか。

しかし、コマ数が増えると急激に難しいパズルになる。もっと難しい、コマ数の多い問題を解こうとしたとき、初期状態とゴール、あるいは途中の通過点を与えるだけでどんな問題でも解くプログラムにしたくなる。

このパズルは、次第に莫大な量の盤面状態をいかにして高速に検索するかが鍵になってくる。保持する必要の無い盤面デ−タは削除してしまいたい。パズルを解いている筈だったのが、いつの間にかデータ処理の研究になってしまう。

このようにして、パズルで遊ぶつもりが、コンピュータ技術も身についてしまうという予想外の事態になる。パズルで遊んでいたつもりが、いつの間にかコンピュータ技術者・研究者になってしまった者は沢山いるのだ。

ナノピコ教室

1969年に共立出版より創刊したコンピュータ雑誌 bit は、当時を代表するコンピュータ技術者が執筆陣に名を連ね、最新のコンピュータ情報を伝える最も優れた雑誌として不動の地位を占めていた。

その雑誌に、『ナノピコ教室』という連載があった。単なる連載ではなく、問題の出題と、その解説で成り立っていた。

問題は、かなり難しいのだが短い問題で、実際にプログラムを組んでもそれほど長くはならない。しかし、下手にプログラムを組むと、どうにもならなくて破綻する、あるいは極端に遅くなるような種類の問題が選ばれていた。

あまりに人気が出たので、『ナノピコ教室』をまとめた本が『ナノピコ教室』(1990年)、『続ナノピコ教室』(1991年) の題名で出された。

それらの付録に、ナノピコ教室の問題、出題者、出題・解答号が示されている。ナノピコ教室の最初の出題が1969年7月号なので、創刊の年に始まっている。

問題は種々雑多であり、いくつかに分類されているのだが、パズルの部がちゃんとある。その中には、以下のようなパズルがある。

トロッコの入れ替え
補助方陣
巡回数
ナンバ−リンク
拾い碁
数独
対応パズル
虫食算
覆面算
ドデカパズル
３次元の女王配置
８パズル空間の直径
カックロ

パズル以外にも、ゲ−ム、組合せという部もあり、出題の約半分はパズルと言い切って問題ないと思う。

しかし、残念なことだが、雑誌bitは多くの往年のコンピュ−タ技術者達に惜しまれながら、 2001年4月号を最終号として休刊になった。これも時代の流れでしかたがない。

練習問題としての利用

このようにして、パズルマニアで、なおかつコンピュータ技術者という人々の間で、静かにパズルプログラミングが浸透していった。

と同時に、プログラム、とくにアルゴリズムという分野を教えるときのテーマとしてパズルを選ぶことが行なわれ出した。アルゴリズムに関する書籍には、本の技術内容を応用すると解ける問題を例題として載せることも珍しくなかった。

Karettaのシリーズの中に『Cパズルプログラミング-再帰編』を用意したが、そこには実際いくつかの代表的な、コンピュータで解くのに都合のよさそうなのを挙げている。

８クイーン
ペグ・ソリテア
ペントミノ
ナンバープレイス

個々に解説を書くのは省略するので、詳しくは、それぞれの説明を読んで欲しい。

パズルの種類は非常に沢山あり、一通り説明しようと思ったら、間違いなく全集ができてしまう。色々なパズルのコンピュータでの解き方を知りたい場合には、現在はネットで調べるのが一番情報が集まるだろう。考え方だけでなく、ソースプログラムも公開されている場合があり、パズルプログラミングを始めたい人にはいくらでも情報が入手可能な状態だ。

速度差

パズルは、プログラムを作る人によって、非常に性能差が出る。上手な人が作ったら非常に高速であるが、下手な人が作ったら解き終えるどころか、永久に計算が終らないとか、暴走してしまって止まらなくなるなど困った情况になる。

コンピュータに処理させるとき、早くて正確であることが重要なのだが、それをはっきり知らしめるには、プログラマの能力差が思いっきり反映されるテーマが最高である。有能な者は評価され、無能な者は打ちひしがれると思うが、実際のプログラム開発の仕事につく前にそれが分かることが望ましい。

どのくらいの差があるか、とりあえず動くプログラムをまず作り、次第に改良し高速にしていった経過を、ペントミノという箱詰めパズルで試した例があったので、その部分だけを以下に引用しておく。

ソースプログラム	実行時間(秒)	方法
pentomino29.c	0.76	32ビットのビット演算
pentomino28.c	1.30	サイズ可変
pentomino26.c	1.33	ゴリゴリ体力だけの書き直し
pentomino25.c	1.54	使用済みピースを調べない
pentomino24.c	1.95	近傍の予備チェック
pentomino23.c	2.49	右隣と下隣のチェック
pentomino22.c	2.98	ピースＸを左上1/4に制限
pentomino21.c	12.47	１次元配列化
pentomino20.c	22.40	ピースＦによる対称性の除去
pentomino19.c	55.78	全部求めてから対称性を除去

１分かかっていたものが、改良することで、１秒を切るようになった。

この程度の改善は、パズルとしては比較的穏やかな改善である。千倍、万倍の改善も珍しくない。

この劇的な速度差が出ることが、コンピュータ技術者がパズルプログラム中毒になる理由だ。

人より上手いプログラムを作ってみたいと思う技術者魂をくすぐるのだ。

大学での利用

以上述べたように、プログラミング、とりわけアルゴリズムを教える、あるいは鍛えるのにパズルは非常に都合が良い。そのため、かなりの数の大学で、公に授業や研究テ−マとして堂々と研究されたり、あるいは教官や学生の趣味としてこっそり研究されている。

大学でどんな感じで使われているか、Googleでちょっと調べてみた。検索オプションで、ドメインを ac.jp(とりあえず日本だけを調べる)とし、キ−フレ−ズとして『パズル』を入れたら、色々な大学が出てきた。

これは実際にはごく一部で、実際にはどのくらい存在するのかよく分からない。

パズルプログラミング自体を授業でやっている場合もあるし、大学院の研究テ−マにしていたり、本来の研究テ−マの実証実験の対象としてパズルが選ばれたり、パズルを選択する理由は色々だが、とにかくパズルをやっていることには違いない。

お堅いと思われている学会の中にも、情報処理学会ゲーム情報学研究会というものがあり、ゲ−ムやパズルに絞った研究会になっている。

このペ−ジを見ていると、著名なコンピュ−タ研究者の名前が並んでいる。こういう人々もパズルやゲームにコンピュータ及び自分の頭脳を惜しげもなく注ぎ込んでいるのだ。

これからも、パズルやゲ−ムを通して情報処理の研究が行なわれ続けるのは間違いないようで、安心してパズルの研究に精を出すことができる。そして、もしかするとコンピュータ技術や人工知能関連の能力が勝手に向上してしまうかもしれない。

なお、色々なパズルやゲームのために公的な研究資金援助を受けたい場合には、上記を参考にしつつも、大義名分を考えて申請書を書いた方が良いらしい。

Home

パズル問題自動生成時代

概論

ナンプレ