解を求めるプログラム

昨日の続きです。iPhone 等で動くチェスのナイト・ツアーのパズルのような無料アプリ Homeless Pony の問題は一通り解きました。普通に自力で解いた後で、これを解くためのプログラムを書き始めたら、それが楽しくて今週末はほとんどそれをやっていました。ちなみに、使ったのは Excel です。

最初はナイトの動きの組み合わせを網羅的に調べさせていました。しかし、それだと7手でも Excel の上限である 1,048,576 行をはるかに超える 2,097,152 通り（8の7乗）の手順があり、遅いし、無駄があります。昨年の夏に開催されていたコンピュータチェスの大会で開発者の一人が読まなくて済む手をいかに除外するかが改良の鍵だと言ってましたが、今日の私はまさに無駄な計算をいかに減らすかの工夫をしていました。一応 解答を出せるまでは作りましたが、ルーク（スケートボード）は難しいので諦めました。

例えば、上のような問題だとしたら、下のように Excel のセルに配置を書いて Solve ボタンを押すと、


上のような解答候補がポップアップで出て来ます。ちょっと見にくいかもしれませんが、この問題には答えが3通りあるということです。別のシートには以下のようなデバッグ情報（プログラムが間違っていないかどうか検証するための情報）も出るようにしています。

妻になぜこのようなものを書いたのか聞かれましたが、パズルを解くのが楽しいのと同じように、パズルを解くアルゴリズムを考えることも私にとっては楽しいのです。チェスの解析プログラムを趣味で書いている人（昨年のコンピュータチェスの大会の参加者）の気持ちが少し分かりました。そこまでやるつもりはありませんけど。