8-2 ナイト巡回問題

問題

バックトラック法

ナイト巡回問題は、与えられたマスを、ナイトが連続して飛び続けることで、
全てのマスを１回ずつ訪れる経路を求める問題である。 

行儀の良くないナイト巡回問題を解いてみます。

ソース

using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Level;
        internal int X;
        internal int Y;
        internal string Path;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();

        JyoutaiDef WillPush;
        WillPush.Level = 1;
        WillPush.X = WillPush.Y = 1;

        WillPush.Path = "(1,1)";
        stk.Push(WillPush);

        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDef WorkJyoutai = stk.Pop();

            if (WorkJyoutai.Level == 5 * 5) {
                System.Console.WriteLine("Answer{0:D3}={1}", ++AnswerCnt, WorkJyoutai.Path);
                continue;
            }

            WillPush.Level = WorkJyoutai.Level + 1;

            int[] moveX = { +1, +2, +2, +1, -1, -2, -2, -1 };
            int[] moveY = { -2, -1, +1, +2, +2, +1, -1, -2 };

            for (int I = 0; I <= moveX.GetUpperBound(0); I++) {
                WillPush.X = WorkJyoutai.X + moveX[I];
                WillPush.Y = WorkJyoutai.Y + moveY[I];

                if (IsValid(WillPush.X, WillPush.Y, WorkJyoutai.Path)) {
                    WillPush.Path = WorkJyoutai.Path + string.Format("({0},{1})", WillPush.X, WillPush.Y);
                    stk.Push(WillPush);
                }
            }
        }
    }

    static bool IsValid(int X,int Y,string Path)
    {
        if (X < 1) return false;
        if (X > 5) return false;
        if (Y < 1) return false;
        if (Y > 5) return false;

        if (Path.Contains(string.Format("({0},{1})",X, Y))) return false;
        return true;
    }
}

実行結果

Answer001=(1,1)(2,3)(1,5)(3,4)(2,2)(1,4)(3,5)(5,4)(4,2)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(1,2)(2,4)(4,5)(3,3)(4,1)(5,3)(3,2)(5,1)(4,3)(5,5)
Answer002=(1,1)(2,3)(1,5)(3,4)(2,2)(1,4)(3,5)(5,4)(4,2)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(1,2)(3,3)(4,1)(5,3)(4,5)(2,4)(3,2)(5,1)(4,3)(5,5)
Answer003=(1,1)(2,3)(1,5)(3,4)(2,2)(1,4)(3,5)(5,4)(4,2)(2,1)(1,3)(2,5)(3,3)(4,1)(5,3)(4,5)(2,4)(1,2)(3,1)(5,2)(4,4)(3,2)(5,1)(4,3)(5,5)
省略
Answer302=(1,1)(3,2)(5,1)(4,3)(5,5)(3,4)(4,2)(5,4)(3,3)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(1,2)(2,4)(4,5)(5,3)(4,1)(2,2)(1,4)(3,5)(2,3)(1,5)
Answer303=(1,1)(3,2)(5,1)(4,3)(5,5)(3,4)(4,2)(5,4)(3,5)(1,4)(2,2)(4,1)(5,3)(4,5)(2,4)(1,2)(3,3)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(2,3)(1,5)
Answer304=(1,1)(3,2)(5,1)(4,3)(5,5)(3,4)(4,2)(5,4)(3,5)(1,4)(2,2)(4,1)(5,3)(4,5)(2,4)(1,2)(3,1)(5,2)(3,3)(2,1)(1,3)(2,5)(4,4)(2,3)(1,5)

解説

下記のように配列の初期化子で符号を明示して、オートフォーマットしても上下がずれないようにしてます。
int[] moveX = { +1, +2, +2, +1, -1, -2, -2, -1 };
int[] moveY = { -2, -1, +1, +2, +2, +1, -1, -2 };