Tour)」を解くプログラムをC++で書いてみた。騎士の巡歴とはチェスボード上の駒「ナイト」を移動させてすべてのマスを一回ずつ通過させる問題だ。一応、C++らしいコードを心掛けてみたけど、思ったより長くなってしまった。騎士の巡歴ではWarnsdorffのアルゴリズム、騎士の周遊においてはそれに加えてSchwenkの定理を用いている。Programmingで書かれている方法も参考にさせてもらった。ボード上のマスをNode構造体のポインタで表現し、*nodeとする。next;として保持する。一度通ったnodeはnode->visitedにそれを記録しておく。nextを順に巡っていくが、Warndorffのアルゴリズムにより、移動先となるnext内のnodeのうち、動けるマスの最も少ないnodeを移動先とする。すべてのマスを通れば探索終了だ。騎士の周遊については、最初にSchwenkの定理から解があるかどうかを判断する。解があれば、騎士の巡歴と同様の手順でまず解を見つける。ここで、見つけた解の最初のマスからナイトが動けるマスをA、最後のマスからナイトが動けるマスをBとし、BからAの順となるマスがあるかどうか調べる。あれば、そのAのマスから最後のマスまでの順路を逆にすればそれが騎士の周遊の解となる。BからAの順となるマスがなければ、動けるマスが見つかるまでバックトラックにより探索する。Programmingが詳しい。プログラムの使い方は以下の通り。0)で、何も指定がなければ騎士の巡歴を求める。16x16マス上で騎士の周遊を解く場合は以下のようにする。5)の位置から騎士の巡歴を解く場合は以下のようにする。8示した画像は出力した解をPython+PILで画像に変換したものだ。以下のように使用する。高さ=400]上記の例では以下のようにする。600また、今回のプログラムでは200x200マスの騎士の周遊でもほぼ瞬時に解くことができた。先頭の画像はその解だ。多くの場合は問題なく解を見つけることができるが、場合によっては困難なこともある。そのようなときはスタート位置を変更することで解けることがある。以下にプログラムのソースコードを示す。Engineメッセージボード*当ブログに関する意見や要望などにお使いください。Googleアカウントでログインすることで書き込みができます。Twitterへの送信を同時に行うこともできます。ストリートビューで散歩*Googleマップのストリートビューを利用して散歩をするWebアプリです。ストリートビューとマップを分割してマーカーを視界タイプに変更することで使いやすくしてあります。APIを利用したグラフ・チャート作成ウェブアプリです。クリック一つで簡単にグラフを作成できます。ブログ記事への貼り付けなどにどうぞ。OpenIDテスト*OpenIDによるログインのテストを行います。mixiであればクリック一つで、他のOpenIDアカウントであればそのURLを入力することでテストできます。一言コメント表示機能付きです。HTML文字変換*テキストで使われているHTML特殊文字をウェブで表示できるようにするための文字変換ウェブアプリです。プログラムのソースコードなどをブログ記事に貼り付けるときなどに便利です。短縮URLチェッカー*フィッシングサイト判別機能付き短縮URLチェッカーです。テキストボックスに変換したいURLを入力すればbit.lyの短縮URLが表示され、bit.lyの短縮URLを入力すればもとのURLが表示されます。展開されたURLがリンク付きで表示されますが、もしフィッシングサイトの疑いがある場合は警告が表示されます。Trendsの急上昇ワードをランキング順に表示します。Googleでのキーワード・画像検索やWikipediaによる用語の説明もあります。※GoogleがAPIの提供を終了したため、現在停止中です。自己紹介noxゲームを楽しむだけの余裕と感性は失いたくないnoxです。