ワンコと双葉

1/5から再開した「旅するナイト」のナゾの調査、30日が経過したので2/5に終了しました。

今回も残念ながら全てを求めることはできませんでした。
しかし、たくさんの解法があることがわかりました。

【調査結果】
—————————————
発見解法 327,657パターン
所要時間 30日
—————————————
ネットで解法を探してみると、自作プログラムが見付けていない解法がいくつもありました。
どうも想像していた以上にたくさんの解法がありそうです。
「旅するナイト」というタイトルですが、古典的なパズルで
「ナイト巡回問題」「ナイトツアー」「Knight’s tour」などの名称で知られています。
効率的に解く解法はわかりましたが、一体いくつの解法があるのか？
インターネットで検索したところ、やっと次の論文を発見。
「The Number of Knight’s Tours Equals 33,439,123,484,294 – Counting with Binary Decision Diagrams (1996)」
M.LöbbingとI.WegenerがBDD法を使って解法の数を求めたそうです。
何と、何兆個もあるそうです！
私のプログラムは1ヶ月で30万個を求めましたが、兆ですかぁ・・・
今のやり方では一生かけても無理なので断念します。
せっかく30万パターン見つけたので、希望者の方がいらっしゃれば解法を公開します。
（解法を記録したファイルサイズはzip形式で8Mバイト程度）
(「旅するナイト」を解いている方にはあまり見せない方がいいかも)
【最後に】
終了を記念して自作プログラムが最初に求めた解法をアニメーションでご紹介します。
下の画像をクリックするとオリジナルサイズ(482×482,10秒程度)でアニメーションを表示します。
単純にナイトが動くアニメーションでもよかったのですが、少し工夫をしてみました。
(リアルなナイトやチェス盤は自分では描けそうもないというのが本当の理由ですが＾＾；）
黄色い「ワンコ」と「双葉」が旅をしてマス目を通っていくと隠された風景が見えてきます。
場所がわかった方は是非コメントくださいませ。

ちなみに私のプロフィール画像(2009/02/07時点)を大きくしただけなんですけどね。
ふぅ。