×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

ナイト(騎士)巡回問題

ナイト巡回問題とは、チェスのナイトを、チェス盤の上を動かし、すべてのマスを通り、
最初の場所に戻ってくる経路を求めるというものです。
「最初の場所に戻ってくる」という制約をつけないバージョンが一般的かもしれませんね。

Solveボタンを押せば、解を求め、その順番に線を引くアニメーションが始まります。


この問題を解くには、

8クィーンパズル
ナイト(騎士)の最適配置
MagicStarを解く
のように、バックトラック法を使います。

このプログラムでは、ナイト開始位置を左上に固定しています。
簡単に解き方を説明すると、

 1. ナイトを動かした場所には、何番目に移動したかを記録する番号を振っておきます。
 2. ナイトを次に動かす場所がなければ、失敗 1へ。
 3. 巡回する前に、開始位置に戻れる場所がすべて埋まってしまったら失敗 1へ。
 4. すべてのマスを通り、もとに戻れる位置にいれば終了(成功)
 5. 1 へ戻る。

とこんな感じです。

もちろん、失敗したときには、後戻りしないといけませんから、再帰処理でこれをやっています。
解は一つだけ求めています。
僕の下手な日本語よりも、コードを読んでいただいたほうが、早いと思います。
KnightTour クラスがこれを担当しています。このクラス自体は、コード量も少なく
それほど複雑なことをしているわけではありません。

そのほかの主要なクラスは、 以下の通りです。

Chessboard : チェス盤を表すクラスで、Boardクラスを継承しています。KnightTourクラスは、
このChessBoardを使い、ナイトを置いたり、取り外したり、何歩目かを記録したりしています。

ChessboardCanvas : チェスボードの描画を担当するクラスで、BoardCanvasクラスを継承しています。
ChessBoardクラスと連携し、何歩目かを表示します。

MainPage : Pageクラスで、ボタンが押された時の処理を記述しています。


アニメーションは、MainPageクラスで行っています。
アニメーションも、ChessboardCanvasで実装したかったのですが、手抜きしてしまいました。

このプログラムで利用している Board, BoardCanvasクラスは、他のプログラムでも利用できるよう
ある程度汎用性を持たせています。Board, BoardCanvasクラスのソースコードはこちらに掲載しています。

以下に、C#+Silverlightのコードを示します。


■KnightTour.cs


■MainPage.xaml.cs


■MainPage.xaml