PL/SQL6 川渡り 農夫と狼とヤギとキャベツ

SQLパズル

この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。

オオカミとヤギを連れキャベツを持った農夫が川岸にいる。
川にはボートがあるが農夫の他には動物一頭かキャベツ一個しか乗せられない。
農夫がいなければオオカミはヤギを襲うし、ヤギはキャベツを食べてしまう。

すべてを無事に対岸に渡すにはどうしたらよいか?

ソース

declare
    type InfoDef is record(
        pNouhu   pls_Integer,
        pOOkami  pls_Integer,
        pYagi    pls_Integer,
        pKyabetu pls_Integer,

        LogPath varchar2(2000),
        LV pls_Integer
    );

    stackP pls_Integer := 0;
    type StackClass is table of InfoDef index by binary_integer;
    st StackClass;
    priInfo  InfoDef;
    willPush InfoDef;
    LoopChk pls_Integer :=0;
    willWrite varchar2(200);
    ansCnt pls_Integer := 0;

    procedure push(pInfoDef InfoDef) is
    begin
        willWrite := '(';
        if (pInfoDef.pNouhu   = 0) then willWrite := willWrite || '人'; end if;
        if (pInfoDef.pOOkami  = 0) then willWrite := willWrite || '狼'; end if;
        if (pInfoDef.pYagi    = 0) then willWrite := willWrite || 'ヤ'; end if;
        if (pInfoDef.pKyabetu = 0) then willWrite := willWrite || 'キ'; end if;
        willWrite := willWrite || '■';
        if (pInfoDef.pNouhu   = 1) then willWrite := willWrite || '人'; end if;
        if (pInfoDef.pOOkami  = 1) then willWrite := willWrite || '狼'; end if;
        if (pInfoDef.pYagi    = 1) then willWrite := willWrite || 'ヤ'; end if;
        if (pInfoDef.pKyabetu = 1) then willWrite := willWrite || 'キ'; end if;
        willWrite := willWrite || ')';

        st(stackP) := pInfoDef;
        st(stackP).LogPath := st(stackP).LogPath || willWrite;
        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;

    function isValid(pInfoDef InfoDef) return boolean is
    begin
        if ((pInfoDef.pNouhu = 0 and pInfoDef.pOOkami = 1 and pInfoDef.pYagi = 1) or
            (pInfoDef.pNouhu = 1 and pInfoDef.pOOkami = 0 and pInfoDef.pYagi = 0) or
            (pInfoDef.pNouhu = 0 and pInfoDef.pYagi   = 1 and pInfoDef.pKyabetu = 1) or
            (pInfoDef.pNouhu = 1 and pInfoDef.pYagi   = 0 and pInfoDef.pKyabetu = 0)) then
            return false;
        end if;
        return true;
    end;

begin
    --Start With句
    willPush.LV := 1;
    willPush.pNouhu := 1;
    willPush.LogPath := null;

    willPush.pOOkami := 0; willPush.pYagi := 0;willPush.pKyabetu := 1; push(willPush);
    willPush.pOOkami := 0; willPush.pYagi := 1;willPush.pKyabetu := 0; push(willPush);
    willPush.pOOkami := 1; willPush.pYagi := 0;willPush.pKyabetu := 0; push(willPush);

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

        -- 合格経路なら表示
        if (priInfo.pNouhu   = 1 and
            priInfo.pOOkami  = 1 and
            priInfo.pYagi    = 1 and
            priInfo.pKyabetu = 1) then
            ansCnt := ansCnt+1;
            DBMS_Output.Put_Line('解' || to_char(ansCnt));
            DBMS_Output.Put_Line(priInfo.LogPath);
        end if;

        priInfo.LV := priInfo.LV+1;

        if (priInfo.LV < 6) then
            if (priInfo.pNouhu = 0) then
                priInfo.pNouhu := 1;
                if (isValid(priInfo)) then push(priInfo); end if;

                if (priInfo.pOOkami = 0) then
                    priInfo.pOOkami := 1;
                    if (isValid(priInfo)) then push(priInfo); end if;
                    priInfo.pOOkami := 0;
                end if;
                if (priInfo.pYagi = 0) then
                    priInfo.pYagi := 1;
                    if (isValid(priInfo)) then push(priInfo); end if;
                    priInfo.pYagi := 0;
                end if;
                if (priInfo.pKyabetu = 0) then
                    priInfo.pKyabetu := 1;
                    if (isValid(priInfo)) then push(priInfo); end if;
                    priInfo.pKyabetu := 0;
                end if;
            else
                priInfo.pNouhu := 0;
                if (isValid(priInfo)) then push(priInfo); end if;

                if (priInfo.pOOkami = 1) then
                    priInfo.pOOkami := 0;
                    if (isValid(priInfo)) then push(priInfo); end if;
                    priInfo.pOOkami := 1;
                end if;
                if (priInfo.pYagi = 1) then
                    priInfo.pYagi := 0;
                    if (isValid(priInfo)) then push(priInfo); end if;
                    priInfo.pYagi := 1;
                end if;
                if (priInfo.pKyabetu = 1) then
                    priInfo.pKyabetu := 0;
                    if (isValid(priInfo)) then push(priInfo); end if;
                    priInfo.pKyabetu := 1;
                end if;
            end if;
        end if;
    end Loop;
end;
/

実行結果

解1
(ヤキ■人狼)(人ヤキ■狼)(ヤ■人狼キ)(人ヤ■狼キ)(■人狼ヤキ)
解2
(狼ヤ■人キ)(人狼ヤ■キ)(ヤ■人狼キ)(人ヤ■狼キ)(■人狼ヤキ)

解説

Oracleの階層問い合わせを意識した、深さ優先探索を使ってます。