1.ナイトツアーとは
ナイトツアーというのは，チェスのナイトの駒でチェスの盤をすべて一度だけ通るというパズルゲームです。レイトン教授のゲームの中にこのパズルゲームがあって，小学生の頃友達と競争していました。イメージがわかない人はWikipediaとか見たり，「ナイトツアー ゲーム」で検索すれば出てきますのでやってみると面白いと思います。
チェスのナイトの動きはこんな感じ。「馬」がナイトです。丸のある場所に移動できます。
注目すべきはこのマスの色。チェスの盤は色が付いているのですが，ナイトは2つの色を交互に移動します（なので盤の色が黒と白ならナイトは黒→白→黒→白と移動します）。両方の色に行けるということは，すべての場所に移動できる可能性があるということです。
ちなみにビショップ（将棋で言う角）は同じ色の上にしかいけません。なのでビショップでこの問題を解くことができないのは容易に証明できます。
今日作ったプログラムはナイトツアーを解くプログラムです。下は5✕5のあるパターンです。数字の順番にナイトが移動すると漏れ無く盤の上を移動できます。
ちなみにコツは外側から攻めてくということです。上の答えも子供の頃にやったまんまの答えです。案外覚えているもんですねｗ。
プログラムが正しければ5✕5の場合は304通りあるはずです。6✕6や7✕7は時間がかかりそうだったのでやりませんでしたが，もし実行して答えが出たという人は教えて下さい。
2.プログラム
再帰関数を使っているからちょっと不安。あまり大きい数字を入れるとスタックオーバーフローとか出てくるかもしれないのでそこはご勘弁を。
/**
* 2015/10/12
* ナイトツアーの数え上げプログラム
*/
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
//5x5のパターンを数え上げる
var nt = new NightTour(5);
Console.WriteLine("Search Start...");
//すべて数え上げる
nt.Start(true);
//一個見つければいい人はこう
//nt.Start(false);
//nt.Show();
Console.WriteLine("Search End...");
}
}
class NightTour
{
/// <summary>
/// 枠の大きさ
/// </summary>
int N = 8;
/// <summary>
/// ボード
/// </summary>
int[,] Board;
/// <summary>
/// ナイトのX座標
/// </summary>
int X;
/// <summary>
/// ナイトのY座標
/// </summary>
int Y;
/// <summary>
/// 答えの個数
/// </summary>
int Count;
/// <summary>
/// コンストラクタ
/// </summary>
/// <param name="N">枠の大きさ</param>
public NightTour(int N)
{
this.N = N;
Board = new int[N, N];
X = 0;
Y = 0;
// 左上を最初の場所にする
Board[0, 0] = 1;
}
/// <summary>
/// 旅を開始するメソッド
/// </summary>
/// <param name="forever">永遠に続けるかどうか</param>
public void Start(bool forever)
{
Count = 0;
Tour(2,forever);
}
/// <summary>
/// 答えを表示するメソッド
/// </summary>
public void Show()
{
Console.WriteLine("Count = {0}",Count);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
Console.Write("{0,5}", Board[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}
/// <summary>
/// ナイトツアーを時効するメソッド
/// </summary>
/// <param name="depth">深さ</param>
/// <param name="forever">永遠に続けるかどうか</param>
/// <returns>旅が終わったかどうか</returns>
private bool Tour(int depth,bool forever)
{
// すべて塗りつくした場合
if (depth > N * N)
{
Count++;
// 永遠に続けるならばここで表示する
if (forever)
Show();
return true;
}
// 移動先を探す
var nextPlace = SearchNextPlace();
if (nextPlace.Length == 0)
return false;
foreach (Tuple<int, int> t in nextPlace)
{
// 現在の状態を保存しておく
int temp_x = X;
int temp_y = Y;
// 移動する
X = t.Item1;
Y = t.Item2;
Board[X, Y] = depth;
//移動先で行動させる
if (forever)
Tour(depth + 1,forever);
else
if (Tour(depth + 1, forever) == true)
return true;
// 元に戻す
Board[X, Y] = 0;
X = temp_x;
Y = temp_y;
}
return false;
}
/// <summary>
/// 移動できる座標を探すメソッド
/// </summary>
/// <returns>移動可能な位置座標</returns>
private Tuple<int, int>[] SearchNextPlace()
{
var ret = new List<Tuple<int, int>>();
// マスの大きさを無視してとりあえず移動先を考える
ret.Add(Tuple.Create(X - 1, Y - 2));
ret.Add(Tuple.Create(X - 1, Y + 2));
ret.Add(Tuple.Create(X + 1, Y - 2));
ret.Add(Tuple.Create(X + 1, Y + 2));
ret.Add(Tuple.Create(X - 2, Y - 1));
ret.Add(Tuple.Create(X - 2, Y + 1));
ret.Add(Tuple.Create(X + 2, Y - 1));
ret.Add(Tuple.Create(X + 2, Y + 1));
// 移動できない場所を削除する
for (int i = 0; i < ret.Count; i++)
{
if (CanMove(ret[i].Item1, ret[i].Item2) == false)
{
ret.RemoveAt(i);
i--;
}
}
// 配列にして返す
return ret.ToArray();
}
/// <summary>
/// 動ける場所かどうかを判定するメソッド
/// </summary>
/// <param name="x">x方向のindex</param>
/// <param name="y">y方向のindex</param>
/// <returns>動ける場所ならばtrue</returns>
private bool CanMove(int x, int y)
{
if (InRange(x, y) == false)
return false;
if (Board[x, y] != 0)
return false;
return true;
}
/// <summary>
/// インデックスが配列の範囲内かどうかを判定するメソッド
/// </summary>
/// <param name="x">x方向のindex</param>
/// <param name="y">y方向のindex</param>
/// <returns>範囲内ならtrue</returns>
private bool InRange(int x, int y)
{
if (x < 0 || x >= N || y < 0 || y >= N)
return false;
return true;
}
}
6✕6とかやった人いるのかなぁ。魔法陣の数え上げは5✕5までだった気がする。こういう数え上げとかは競技プログラミングっぽくてもっといい方法がありそうな気がする。
