PL/SQL3 ナイト巡回問題

SQLパズル

バックトラック法

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

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

データ作成スクリプト

create table ban(X,Y) as
select 1,1 from dual union
select 1,2 from dual union
select 1,3 from dual union
select 1,4 from dual union
select 1,5 from dual union
select 2,1 from dual union
select 2,2 from dual union
select 2,3 from dual union
select 2,4 from dual union
select 2,5 from dual union
select 3,1 from dual union
select 3,2 from dual union
select 3,3 from dual union
select 3,4 from dual union
select 3,5 from dual union
select 4,1 from dual union
select 4,2 from dual union
select 4,3 from dual union
select 4,4 from dual union
select 4,5 from dual union
select 5,1 from dual union
select 5,2 from dual union
select 5,3 from dual union
select 5,4 from dual union
select 5,5 from dual;

SQL

select sys_connect_by_path(to_char(X) || to_char(Y),'-') as path
  from ban
 where connect_by_IsLeaf = 1
   and Level = 25
   and RowNum <=10
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);
    LoopChk pls_Integer :=0;
    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 (isOK) then
                DBMS_Output.Put_Line(priInfo.Path);
            end if;
        end if;

        LoopChk := LoopChk+1;
        if (LoopChk=99999) then
            DBMS_Output.Put_Line('CountStop!!!');
            exit;
        end if;
    end Loop;
end;
/

実行結果

(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)
CountStop!!!

解説

PL/SQLよりも、Javaのほうが速く終了しましたねぇ