2-3 ナイト巡回問題

Javaアルゴリズムパズル

バックトラック法

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

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

ソース

public final class badKnight {

    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) {
        badKnight mi = new badKnight();
        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 (isOK) System.out.println(priInfo.Path);
            }

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

実行結果

(1,1)-(3,2)-(5,3)-(4,5)-(2,4)-(1,2)-(3,3)-(4,1)-(2,2)-(1,4)-(3,5)-(5,4)-(4,2)-(2,1)-(1,3)-(2,5)-(4,4)-(5,2)-(3,1)-(2,3)-(1,5)-(3,4)-(5,5)-(4,3)-(5,1)
(1,1)-(3,2)-(5,3)-(4,5)-(2,4)-(1,2)-(3,1)-(5,2)-(4,4)-(2,5)-(1,3)-(2,1)-(4,2)-(5,4)-(3,3)-(4,1)-(2,2)-(1,4)-(3,5)-(2,3)-(1,5)-(3,4)-(5,5)-(4,3)-(5,1)
(1,1)-(3,2)-(5,3)-(4,5)-(2,4)-(1,2)-(3,1)-(5,2)-(4,4)-(2,5)-(1,3)-(2,1)-(3,3)-(4,1)-(2,2)-(1,4)-(3,5)-(5,4)-(4,2)-(2,3)-(1,5)-(3,4)-(5,5)-(4,3)-(5,1)
(1,1)-(3,2)-(5,3)-(4,5)-(2,4)-(1,2)-(3,1)-(5,2)-(3,3)-(4,1)-(2,2)-(1,4)-(3,5)-(5,4)-(4,2)-(2,1)-(1,3)-(2,5)-(4,4)-(2,3)-(1,5)-(3,4)-(5,5)-(4,3)-(5,1)
以下省略