Pongeponge

騎士巡回問題

シドニアの騎士(1)

 騎士巡回問題とかいうのがある。
簡単に言うと、
『チェスのナイトが、盤面の全てのマスを踏んで元の位置に戻る』ルートを探せ
という問題。



KnightsKnights / John-Morgan
ナイトの嫌なところ
 動きが嫌。
駒の動き方 - 日本チェス協会
将棋を知ってるのなら、桂馬の動きと言えばわかりますかね。
駒の名前と動き方【桂馬(けいま)と成桂(なりけい)】
まっすぐ動けばいいのにちょっとズレる。
なんとも微妙な動きをするわけです。



White KnightWhite Knight / John-Morgan
C#で作ってみた
 「全マス踏んで元の位置に戻る」条件を緩めて、「全マス踏む」だけにした。
easyモード最高。
ソースコードは下に書くとして、盤面5×5、中央スタートでの実行結果がこちら。
19213825
12718314
17201249
61122154
211651023
中央の1からスタートして、2,3,4…と進んで、25で終了。
Unityに移植して駒を実際に動かしたら見た目もよさそう……まぁ、別の機会に。



Knights in CombatKnights in Combat / Jeff Kubina
再起で探索してるけど…
 数式でババーンと「こういう経路があります!」ってできないもんだろうか?
ペロッと書ける数式があれば便利なんだけどな。



ソースコードはこんな感じ。

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());
        }

    }
}