PL/SQL4 (行儀の良い)ナイト巡回問題

SQLパズル

バックトラック法

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

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

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

SQL

create table goodKnightResult as
select sys_connect_by_path(to_char(X) || to_char(Y),'-') as path
  from ban
 where connect_by_IsLeaf = 1
   and Level = 25
   and (X=3 and Y=2
     or X=2 and Y=3)
Start With 1 = all(X,Y)
connect by nocycle (prior X,prior Y)
                in ((X+2,Y-1),(X+2,Y+1),
                    (X-2,Y+1),(X-2,Y-1),
                    (X+1,Y+2),(X+1,Y-2),
                    (X-1,Y+2),(X-1,Y-2));

PL/SQL

declare
    masu constant pls_Integer := 5;

    type InfoDef is record(
        X pls_Integer,
        Y pls_Integer,
        LV pls_Integer,
        Path varchar2(1000)
    );

    stackP pls_Integer := 0;
    type StackClass is table of InfoDef index by binary_integer;
    st StackClass;
    StaInfo  InfoDef;
    priInfo  InfoDef;
    willPush InfoDef;
    work varchar2(20);
    isOK boolean;

    procedure push(pInfoDef InfoDef) is
    begin
        st(stackP) := pInfoDef;
        stackP := stackP+1;
    end;

    function pop return InfoDef is
    begin
        stackP := stackP-1;
        return st(stackP);
    end;

    function isEmpty return boolean is
    begin
        return stackP = 0;
    end;

begin
    StaInfo.X  := 1; StaInfo.Y := 1;
    StaInfo.LV := 1; StaInfo.Path := '(1,1)';

    push(StaInfo);

    while (isEmpty = false) loop
        priInfo := pop();

        for X in 1..masu Loop
            for Y in 1..masu Loop

                if (((priInfo.X+2 = X and priInfo.Y+1 = Y)
                or (priInfo.X+2 = X and priInfo.Y-1 = Y)
                or (priInfo.X+1 = X and priInfo.Y+2 = Y)
                or (priInfo.X+1 = X and priInfo.Y-2 = Y)
                or (priInfo.X-2 = X and priInfo.Y+1 = Y)
                or (priInfo.X-2 = X and priInfo.Y-1 = Y)
                or (priInfo.X-1 = X and priInfo.Y+2 = Y)
                or (priInfo.X-1 = X and priInfo.Y-2 = Y)) and priInfo.LV < masu*masu) then

                    work := '(' || to_char(X) || ',' || to_char(Y) || ')';

                    --未到着ノードならpush
                    if (instr(priInfo.Path,work) = 0) then
                        willPush.Path:= priInfo.Path || '-' || work;
                        willPush.X := X; willPush.Y := Y;
                        willPush.LV := priInfo.LV+1;
                        push(willPush);
                    end if;
                end if;
            end Loop;
        end Loop;

        --合格経路なら表示
        if (priInfo.LV = masu*masu) then
            isOK := true;
            for X in 1..masu Loop
                for Y in 1..masu Loop
                    work := '(' || to_char(X) || ',' || to_char(Y) || ')';
                    if (instr(priInfo.Path,work) = 0) then
                        isOK := false;
                    end if;
                end Loop;
            end Loop;

            if (priInfo.X = 3 and priInfo.Y = 2
             or priInfo.X = 2 and priInfo.Y = 3) then
                null;
            else
                isOK := false;
            end if;

            if (isOK) then
                DBMS_Output.Put_Line(priInfo.Path);
            end if;
        end if;
    end Loop;
end;
/

解説

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