騎士巡回問題とかいうのがある。
簡単に言うと、
『チェスのナイトが、盤面の全てのマスを踏んで元の位置に戻る』ルートを探せ
という問題。
ナイトの嫌なところ
動きが嫌。
駒の動き方 - 日本チェス協会
将棋を知ってるのなら、桂馬の動きと言えばわかりますかね。
駒の名前と動き方【桂馬(けいま)と成桂(なりけい)】
まっすぐ動けばいいのにちょっとズレる。
なんとも微妙な動きをするわけです。
C#で作ってみた
「全マス踏んで元の位置に戻る」条件を緩めて、「全マス踏む」だけにした。
easyモード最高。
ソースコードは下に書くとして、盤面5×5、中央スタートでの実行結果がこちら。
19 | 2 | 13 | 8 | 25 |
---|---|---|---|---|
12 | 7 | 18 | 3 | 14 |
17 | 20 | 1 | 24 | 9 |
6 | 11 | 22 | 15 | 4 |
21 | 16 | 5 | 10 | 23 |
Unityに移植して駒を実際に動かしたら見た目もよさそう……まぁ、別の機会に。
再起で探索してるけど…
数式でババーンと「こういう経路があります!」ってできないもんだろうか?
ペロッと書ける数式があれば便利なんだけどな。
ソースコードはこんな感じ。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Diagnostics; using System.Drawing; namespace kishijyunkai { class Program { static void Main(string[] args) { Night n = new Night(); n.start(5, 5, 2, 2); n.DarwField(); } } class Night { //盤面のサイズ int xsize; int ysize; //盤面 int[,] field; //マス目の総数 int c; //移動8方向 Point[] move = { new Point(-2, -1), new Point(-2, 1), new Point(-1, -2), new Point(-1, 2), new Point(1, -2), new Point(1, 2), new Point(2, -1), new Point(2, 1)}; /// <summary> /// 開始 /// </summary> /// <param name="xs">盤面の横サイズ</param> /// <param name="ys">盤面の縦サイズ</param> /// <param name="px">スタートx座標</param> /// <param name="py">スタートy座標</param> public void start(int xs, int ys, int px, int py) { //盤面のサイズ取得 this.xsize = xs; this.ysize = ys; //盤面のサイズ決定 this.field = new int[xs, ys]; //目の総数決定 c = xs * ys; loot(1, new Point(px,py)); } public int loot(int step, Point now) { //現在位置にステップ数を記録 field[now.X, now.Y] = step; //ステップ数=目の総数の場合 if (step == c) return c; //確認用 //DarwField(); foreach (Point p in move) { //次の位置 Point next = new Point(now.X + p.X, now.Y + p.Y); //盤面からはみ出ない&ステップ未記入の場合 if ((next.X < xsize && next.X >= 0) && (next.Y < ysize && next.Y >= 0) && (field[next.X, next.Y] == 0)) { //ステップを1増やして次へ step = loot(++step, next); //ステップ数=目の総数の場合 if (step == c) return c; } } //どこにも行けない場合 field[now.X, now.Y] = 0; return --step; } public void DarwField() { StringBuilder sb = new StringBuilder(); for (int x = 0; x < this.xsize; x++) { for (int y = 0; y < this.ysize; y++) { sb.AppendFormat("{0,3}", field[x, y]); } sb.AppendLine(""); } Debug.WriteLine(sb.ToString()); } } }