停電で涙を流す

レイトン教授と悪魔の箱「8×8の旅するナイトのナゾ」

このナゾの解法をプログラムで探索していました。

昨日(1/4)で18日目に入り、もうすぐ6万手が見つかりそうだというところで、パソコンの電源が抜かれ停電となり終了してしまいました。

ガ～ン・・・少しだけ涙

シェイバーの電源を抜く時に誤ってパソコンがつながっているテーブルタップを抜いてしまったのです・・・

年賀状の時のブレーカといい、電源関係のトラブルが多いなぁ。

くやしいので、プログラムを少し修正して再チャレンジさせています。
18日たったら追いつけるはずです(今回は少しだけ早いかな)。

解法がいくつあるのかはわかないので、終わらないかもしれません。
とりあえず実行してみましょう！

結果がすべて出てから「解法の数」と「所要時間」を添えてプログラムを公開しようと思っていたのですが、
そこまで先送りする意味もないので、実際に使っているプログラム一式を公開します。

VisualStudio2005でVB.NETを使って作成しました。
WindowsXP,WindowsVistaで動くと思います(Vistaは未確認ですが)。
腕に覚えがある方、いろいろチャレンジしたい方は改造して使ってください。
無保証ですが、ご自由にどうぞ。許可も何もいりません。商用可です。
なお、動作保証や質問への返答はありませんのであしからず。

プログラムの実行中の画面はこんなです。
(注)くれぐれも8×8にいきなり挑戦しないこと


私も、僕もやってみよう、という方はどうぞご利用ください。
実行中はWindowsUpdateで再起動したりしないように気をつけてください。

インストールプログラム、ソースプログラム一式

私より先に答えが見つかったら是非コメントください。お待ちしています！

この題材は結構勉強のネタになるんじゃないかと思います。

・VB.NETのかわりにC++で書いてみる
・再帰を使わずに解いてみる
・スレッド化して高速化
・ネットワークで複数のコンピュータをつないで並行して解く

なんてこともできるでしょう。

解法についても、
・解法のエレガントさを評価する方法を考えたり
・解法を見せる方法を考えたり
いろいろ思いつきます。ビジネス向きではありませんが、考えることのネタにはなります。

そうそう、気になる(なりませんか？)解法は5万手以上は間違いなくあります。
手元に記録として残っているのは49806手だけですが・・・
求める盤は8×8の正方行列なので、左上～右下に向かって斜め線の所に鏡を置くとわかりますが、
右上からスタートする解法のみを求めればよく、調べる解法は半分になります。
そのため、実際の解法は求めた数の2倍となります。

6×6とかは数分で求まりますが、8×8は手ごわいですよ。7×7は試したことがありません。

あと、総当りなので、相当時間がかかることを覚悟してください。
何十年かけても終わらないかもしれません。
私はとりあえず30日は走らせてみるつもりです。

ミス解法というか、8×8の探索中に行き止まりになる手数は、7000億手まで発見しました。
今週中に1兆手を見られなかったのだけが残念でした。

私は、今年から夜は開発者、昼間は営業マンですので、これから開発者に戻ります。
（夕方は自由人です）

では、みなさんの健闘を祈ります！

[2009/01/25追記]
パズルの名前が誤っていたので修正
「空飛ぶナイト」→「旅するナイト」