騎士巡回問題ソースコード

 コードがごちゃっとしてて分かりにくかったので、できる範囲で分かり易く改善してみた。
system.drawingのPointは演算子に対応してないから手作り。


たぶんきっとちょっとは見やすくなったはず。


 作ってて色々考えたことは、
・ナイトがまっすぐ進んでると考えると、盤面がくるくる回転してるということ。
・出発地点から出て、全部のマスを踏んで出発地点に戻ってくるということは、
 馬は円上をぐるりと回って帰ってくることに等しい。
・帰ってくるということは、右に一回動くなら、どこかで左に一回分動いてプラマイゼロになるはず
・最初を1ステップとして、盤面を奇数と偶数に分けると、市松模様になる
・全部踏む組み合わせって盤面のサイズとどういう関係があるんだろう?
・ナイトが増えたら…?
・盤面が正方形じゃなければ…?
・2次元じゃなくて3,4…n次元と増やしていったら、全部踏むパターンはどう変化するんだろう?
・開始地点変えるだけで解の数が違う
・この場所にナイトが来るなら、ここには絶対に来ないから探索は不必要、っていうのはないん?
・解の数って、全パターン引く何か引く何か引く…で出るかな?
・Unityに移植しようとしたらSystem.drawingがどうとか、stringbuilderがどうとか言われて困る

 

using System;
using System.Diagnostics;

namespace kishijyunkai
{
    class Program
    {
        static void Main(string[] args)
        {
            Night n = new Night();
            n.start(5, 5, 2, 2);
        }

    }

    class Night
    {
        chessboard board;

        //移動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)};

        int count = 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.board = new chessboard(xs, ys);

            loot(1, new point(px, py));
        }


        public void loot(int step, point now)
        {
            //現在位置に番号が既にあれば戻る
            if (this.board.board[now.x, now.y] != 0) return;

            //現在位置にステップ数を記録
            this.board.WriteNumber(now, step);

            //全て踏んだ場合
            if (step == this.board.sumCells)
            {
                Debug.WriteLine("Cong! "+count);
                this.board.Draw();
                count++;
            }

            //確認用
            //this.board.Draw();

            foreach (point p in move)
            {
                //次の位置
                point next = now + p;

                //盤面からはみ出ない&ステップ未記入の場合
                if ((next.x < this.board.width && next.x >= 0) && (next.y < this.board.height && next.y >= 0))
                {
                    //ステップを1増やして次へ
                    loot(step+1, next);
                }
            }

            //どこにも行けない場合
            this.board.WriteNumber(now, 0);
            return;
        }

        //inner class
        public class point
        {
            public int x;
            public int y;

            public point(int X, int Y)
            {
                this.x = X;
                this.y = Y;
            }

            public static point operator +(point a, point b)
            {
                return new point(a.x + b.x, a.y + b.y);
            }
        }

        public class chessboard
        {
            public int[,] board;   //盤面
            public int width;      //幅
            public int height;     //高さ
            public int sumCells;   //目の総数

            public Boolean isInit = false; //初期化フラグ

            //初期化
            public chessboard(int w, int h)
            {
                this.board = new int[w, h];
                this.width = w;
                this.height = h;
                this.sumCells = w * h;
                this.isInit = true;
            }

            //盤面に数字を打つ
            public void WriteNumber(point p, int n)
            {
                if (this.isInit == false) return;
                this.board[p.x, p.y] = n;
            }

            //描画
            public void Draw()
            {
                string str = "";
                Boolean isTable = false;

                if (isTable) str += String.Format("{0}{1}", "<table>", System.Environment.NewLine);
                for (int y = 0; y < this.height; y++)
                {
                    if (isTable) str += "<tr>";
                    for (int x = 0; x < this.width; x++)
                    {
                        if (isTable) str += "<th>";
                        str += String.Format("{0,3}", this.board[x, y]);
                        if (isTable) str += "</th>";
                    }
                    if (isTable) str += "</tr>";
                    str += System.Environment.NewLine;
                }
                if (isTable) str += String.Format("{0}{1}", "</table>", System.Environment.NewLine);

                Debug.WriteLine(str);
            }

        }

    }
}