2-4 (行儀の良い)ナイト巡回問題

Javaアルゴリズムパズル

バックトラック法

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

行儀の良いナイト巡回問題では、最後に元に戻れるように巡回する。
つまり、最後のマスから、最初のマスへは「ナイト飛び」で移動できるものを指す。

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

ソース

//行儀の良いナイト巡回問題
public final class goodKnight {

    final static int masu = 5;

    class InfoDef {
        int X;
        int Y;
        InfoDef(int X,int Y){
            this.X = X;
            this.Y = Y;
        }
        int LV;
        String Path; //sys_connect_by_path用
    };

    //スタック
    class StackClass {
        int stackP;
        InfoDef stackValue[];

        StackClass(){
            stackP = 0;
            stackValue = new InfoDef[99999];
        }

        private void push(InfoDef pInfoDef){
            stackValue[stackP++] = pInfoDef;
        }
        private InfoDef pop(){
            return stackValue[--stackP];
        }
        boolean isEmpty(){
            return stackP == 0;
        }
    }

    public static void main(String[] args) {
        goodKnight mi = new goodKnight();
        mi.main();
    }

    void main() {
        StackClass st = new StackClass();

        InfoDef StaInfo = new InfoDef(1,1);
        StaInfo.LV = 1;
        StaInfo.Path = "(1,1)";
        st.push(StaInfo);

        int LoopChk = 0;
        while (st.isEmpty() == false){
            InfoDef priInfo = st.pop();

            for (int X=1;X<=masu;X++)
                for (int Y=1;Y<=masu;Y++){

                    String Work = "(" + Integer.toString(X) + "," + Integer.toString(Y) + ")";

                    if ((((priInfo.X+2 == X) && (priInfo.Y+1 == Y))
                      || ((priInfo.X+2 == X) && (priInfo.Y-1 == Y))
                      || ((priInfo.X+1 == X) && (priInfo.Y+2 == Y))
                      || ((priInfo.X+1 == X) && (priInfo.Y-2 == Y))
                      || ((priInfo.X-2 == X) && (priInfo.Y+1 == Y))
                      || ((priInfo.X-2 == X) && (priInfo.Y-1 == Y))
                      || ((priInfo.X-1 == X) && (priInfo.Y+2 == Y))
                      || ((priInfo.X-1 == X) && (priInfo.Y-2 == Y)))
                      && priInfo.LV < masu*masu){

                        //未到着ノードならpush
                        if (priInfo.Path.indexOf(Work) == -1){
                            InfoDef willPush = new InfoDef(X,Y);
                            willPush.Path = priInfo.Path + "-" + Work;
                            willPush.LV = priInfo.LV+1;
                            st.push(willPush);
                        }
                    }
            }

            //合格経路なら表示
            if (priInfo.LV == masu*masu){
                boolean isOK = true;
                for (int LX=1;LX<=masu;LX++)
                    for (int LY=1;LY<=masu;LY++){
                    String wk = "(" + Integer.toString(LX) + "," + Integer.toString(LY) + ")";
                    if (priInfo.Path.indexOf(wk) == -1) isOK = false;
                }

                if ((priInfo.X == 3 && priInfo.Y == 2)
                 || (priInfo.X == 2 && priInfo.Y == 3));
                else isOK = false;

                if (isOK) System.out.println(priInfo.Path);
            }

            if (++LoopChk == 99999999){
                System.out.println("There is a Loop."); break;
            }
        }
    }
}

実行結果

条件を満たす経路は存在しませんでした。