ナイト巡回問題とは、チェスを使った数学的パズルの一種。チェスで使う駒のひとつナイトをチェス盤の上を動かし、すべてのマスを1回ずつ通って最初の場所に戻ってくるようにするのはどうすればよいかという問題です。
ナイトは将棋の桂馬のような動きをしますが、桂馬と違うのは前方の2箇所ではなく全方向8箇所に移動できることです。将棋もチェスも知らんがなという方には申し訳ありませんが、これは知っているという前提で話を進めます。
Contents
バックトラック法で解く
一方、バックトラック法とは問題の解を見つけるために解の候補をすべて調べることを組織的にかつ効率よく行うための技法である。簡単にいえば「とりあえずやってみる。失敗したら後戻りしてやり直す」ということです。ウジウジ考えても分からないものはわからないので、とりあえずやってみろ、失敗したらそのとき考えよ（ちょっと違うか？）ということです。
最初はナイトは隅におきます。ここから桂馬飛びに移動します。移動できる部分は2箇所ありますが、ここは適当に選びます。そして移動したあとまた桂馬飛びで移動できる場所が複数あるのですが、ここもどれか一つを適当に選んで次に進みます。これだとどこかでどこへもいけなくなってしまうのですが、この場合はひとつ戻って別の候補を探します。ひとつ戻っただけでは別の候補が見つからない場合はさらにもうひとつ戻ります。
Positionクラス
最初にPositionクラスを作成します。これは座標を管理するためのクラスです。
|
1 2 3 4 5 6 7 8 9 10 11 |
public class Position { public Position(int x, int y) { X = x; Y = y; } public int X = 0; public int Y = 0; } |
Nodeクラス
次にNodeクラスを作成します。Nodeクラスの役割はナイトの現在位置、次の移動先を探して新しいNodeクラスのインスタンスを生成することです。次の移動先を探そうとしても見つからない場合はバックしなければならないので自分自身を作成したNodeへの参照もフィールド変数に含めます。
フィールド変数は以下のとおりです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
public class Node { // 自分自身を生成したNode Node Parent = null; // ナイトの現在位置のX座標とY座標 int CurX = 0; int CurY = 0; // 生成されたインスタンスでナイトの次の移動場所を探すために必要となるマップ int[,] Map = null; // ナイトのスタート位置のX座標とY座標（これは全インスタンス共通の値） int StartX = 0; int StartY = 0; // チェス盤の縦横のマス目の数（通常は8） int RowMax = 0; int ColumMax = 0; // ナイトが次に移動する座標のリスト List<Position> Nexts = new List<Position>(); // ナイトがスタート地点から移動する座標のリスト List<Position> NextsFromStart = new List<Position>(); // 処理を二重に行なわないようにするためのフラグ bool Done = false; } |
コンストラクタは以下のようになります。引数がたくさんありますが、上記のフィールド変数を初期化するために必要なデータです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class Node { public Node(Node parent, int curX, int curY, int number, int[,] map, int startX, int startY, int rowMax, int columMax) { RowMax = rowMax; ColumMax = columMax; Parent = parent; // 引数として渡された二次元配列 mapのコピーをつくる Map = new int[rowMax, columMax]; for (int y = 0; y < rowMax; y++) { for (int x = 0; x < columMax; x++) { Map[y, x] = map[y, x]; } } // このインスタンスが生成されたときのナイトの座標をセット Map[curY, curX] = number; CurX = curX; CurY = curY; // 移動は何回目？ Number = number; // ナイトが最初にあった座標とそこから移動できる座標のリスト // これを考慮外とするとすべてのマス目が埋まったとき、 // ナイトが最初の位置に戻ってこれないものも解として扱われる StartX = startX; StartY = startY; NextsFromStart = GetFirstNexts(); } // Numberは一度セットされたら変更されることはない public int Number { private set; get; } } |
ナイトの最初の位置から移動できる座標のリストを取得する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public class Node { List<Position> GetFirstNexts() { List<Position> positions = new List<Position>(); int x, y; x = StartX - 1; y = StartY - 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX + 1; y = StartY - 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX - 1; y = StartY + 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX + 1; y = StartY + 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX - 2; y = StartY - 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX - 2; y = StartY + 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX + 2; y = StartY - 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); x = StartX + 2; y = StartY + 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0) positions.Add(new Position(x, y)); return positions; } } |
現在位置から移動できる座標のリストを取得する
ナイトが現在位置から移動できる座標のリストを取得するための処理を示します。引数付きのGetNextsメソッドを2回使っています。現在位置から移動できる座標のリストを取得したうえで、さらにその位置から移動できる座標のリストを取得し、リストの要素数が少ない順にソートしています。これが重要な処理らしく、これをやらないと実行時間が極端に長くなり、いつまで経っても終わりません。候補が少ないものから調べて無駄に多く調べることを避けています。
これはソートの処理をしない場合の動画です。上記の動画は比較的簡単に解が見つかりましたが、この動画ではいつまでたっても終わりそうにありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
public class Node { void GetNexts() { if (Done) return; Done = true; Nexts = GetNexts(CurX, CurY); Nexts = Nexts.OrderBy(x => GetNexts(x.X, x.Y).Count).ToList(); } List<Position> GetNexts(int curX, int curY) { List<Position> positions = new List<Position>(); int x, y; x = curX - 1; y = curY - 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX + 1; y = curY - 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX - 1; y = curY + 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX + 1; y = curY + 2; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX - 2; y = curY - 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX - 2; y = curY + 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX + 2; y = curY - 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); x = curX + 2; y = curY + 1; if (x >= 0 && y >= 0 && x < ColumMax && y < RowMax && Map[y, x] == 0 && CanLastPut(x, y)) positions.Add(new Position(x, y)); return positions; } } |
ナイトが最初の場所に戻れないものは却下
ナイトがすべてのマス目を通って最初の場所に戻ってくるためには最後のとき以外はナイトが最初に移動できる位置のどれか一つをあけておかなければなりません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Node { bool CanLastPut(int x, int y) { // これで最後なら何であってもtrue if (Number == ColumMax * RowMax - 1) return true; // それ以外の場合は戻ってくるために空けておかなければならない場所に移動してはならない // x == nextFromStart.X && y == nextFromStart.Yを満たさないものがひとつでもあればOK foreach (var nextFromStart in NextsFromStart) { if (x == nextFromStart.X && y == nextFromStart.Y) continue; else return true; } return false; } } |
移動の処理
移動先の座標のリストを取得することができたら、そのなかからひとつを選び、実際に移動します。そのときはリストの先頭から選び、先頭の要素はRemoveします。そうしないとなんども同じ場所を調べるループから抜けられなくなります。
引数なしのGetNextsメソッドを実行してNextsに移動先のリストが格納されるのは最初に実行したときだけです。2回目以降はなにもおきません。これもそのようにしておかないとなんども同じ場所を調べるループにハマってしまいます。
もしNextsが空のときはこれ以上前には進めないのでバックすることになります。このメソッドがnullを返す場合としてバックバックを繰り返して最初の位置に戻ってしまった場合とすべてのマス目を通って最初の位置に戻ってこれた場合があります。
最初の位置に戻ってしまった場合は解は存在しないことになります。そうでない場合はこれが求めている解のひとつを得たことになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Node { public Node GetNext() { if (Number == RowMax * ColumMax) return null; GetNexts(); if (Nexts.Count > 0) { int next = Number + 1; Position pos = Nexts[0]; Nexts.RemoveAt(0); // 選択した候補は取り除く return new Node(this, pos.X, pos.Y, next, Map, StartX, StartY, RowMax, ColumMax); } else { return Parent; } } } |
結果取得用のメソッド
GetMapメソッドも作りました。使用目的としては処理が終わったときにナイトはどのような順番で移動したかを調べたり、途中経過がどうなっているかを調べることが考えられます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class Node { // 改ざん防止のため二次元配列そのものではなくそのコピーを返す public int[,] GetMap() { int[,] map = new int[RowMax, ColumMax]; for (int y = 0; y < RowMax; y++) { for (int x = 0; x < ColumMax; x++) { map[y, x] = Map[y, x]; } } return map; } } |
KnightTourクラス
次にナイト巡回問題を解くためのKnightTourクラスをみてみましょう。フィールド変数は現在ナイトが存在するNodeを知るためのCurNodeと何回Node.GetNextメソッドを実行したかをカウントするCountがあります。
コンストラクタの引数はチェス盤の縦横のマス目の数、ナイトが最初に存在する座標です。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public class KnightTour { Node CurNode = null; public int Count = 0; public KnightTour(int rowMax, int columMax, int startX, int startY) { int[,] map = new int[rowMax, columMax]; Node start = new Node(null, startX, startY, 1, map, startX, startY, rowMax, columMax); CurNode = start; } } |
MoveNextメソッドはCurNodeからGetNextメソッドを呼び出し、戻り値をCurNodeに格納し直します。GetCurNodeMapメソッドはCurNode.GetMapメソッドの戻り値である二次元配列を返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class KnightTour { public Node MoveNext() { Node node = CurNode.GetNext(); if (node != null) { Count++; CurNode = node; return node; } return null; } public int[,] GetCurNodeMap() { return CurNode.GetMap(); } } |
GetResultメソッドはMoveNextメソッドをnullを返すまで実行し続けて、最後にCurNode.GetMapメソッドの戻り値を返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public class KnightTour { public int[,] GetResult() { while (true) { if (MoveNext() == null) break; } return CurNode.GetMap(); } } |
WindowsFormsアプリケーションで使ってみる
これだけあればバックトラック法でナイト巡回問題を解くことができます。最初はボタンを押したらKnightTour.MoveNextメソッドが1回だけ実行され、そのときにナイトがスタート位置からどのように移動しているかをRichTextBoxに番号で表示させるものをつくります。
GetMapTextメソッドは二次元配列をテキストに変換してRichTextBoxに表示させる文字列を取得するためのものです。
何回かボタンを押していると案外続くことがわかります。そして次に移動できる場所がなくなるとひとつバックして別の解を探そうとしていることがわかります。
これはそれを可視化した動画です。Labelを使って途中経過を表示させているので、ここに掲載しているものとは別のコードで動かしています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public partial class Form1 : Form { public Form1() { InitializeComponent(); label1.Text = ""; } KnightTour KnightTour1 = new KnightTour(8, 8, 0, 0); private void ButtonNext_Click(object sender, EventArgs e) { KnightTour1.MoveNext(); int[,] result = KnightTour1.GetCurNodeMap(); richTextBox1.Text = GetMapText(result); label1.Text = "試行回数 " + KnightTour1.Count.ToString(); } string GetMapText(int[,] map) { StringBuilder sb = new StringBuilder(); for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) { if(map[y, x] > 0) sb.Append(String.Format("{0,2}, ", map[y, x])); else sb.Append(" -, "); } sb.Append("\n"); } return sb.ToString(); } } |
動作をひとつずつ確認するのではなく、すぐに解を表示させる方法も用意しました。処理は一瞬で終わりますが、Nodeクラスの引数なしのGetNextsメソッド内でのソート処理をしていないととんでもなく時間がかかります。
|
1 2 3 4 5 6 7 8 9 10 11 |
public partial class Form1 : Form { private void ButtonAll_Click(object sender, EventArgs e) { KnightTour knightTour = new KnightTour(8, 8, 0, 0); int[,] result = knightTour.GetResult(); richTextBox1.Text = GetMapText(result); label1.Text = "試行回数 " + knightTour.Count.ToString(); } } |
