PL/SQL7 数独

SQLパズル

数独を解きます。

ソース

declare
    type yoko is varray(9) of pls_Integer;
    type BanDef is varray(9) of yoko;
    Ban BanDef :=BanDef(yoko(0,8,0,7,0,1,0,5,0),
                        yoko(0,0,2,0,4,0,9,0,0),
                        yoko(9,3,0,0,0,0,0,7,4),
                        yoko(8,0,0,1,0,4,0,0,6),
                        yoko(0,0,6,0,0,0,1,0,0),
                        yoko(7,0,0,9,0,3,0,0,8),
                        yoko(2,4,0,0,0,0,0,1,5),
                        yoko(0,0,7,0,5,0,3,0,0),
                        yoko(0,5,0,8,0,7,0,4,0));

    stackP binary_integer := 0;
    type StackClass is table of BanDef index by binary_integer;
    st StackClass;

    targetX pls_Integer; targetY pls_Integer;

    procedure push(pBan BanDef) is
    begin
        st(stackP) := pBan;
        stackP := stackP+1;
    end;

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

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

    procedure printBan(pBan BanDef) is
    willOut varchar2(400);
    begin
        DBMS_Output.Put_Line('-----------------');
        for X in 1..9 Loop
            willOut := null;
            for Y in 1..9 Loop
                willOut := willOut || pBan(X)(Y) || ',';
            end Loop;
            DBMS_Output.Put_Line(willOut);
        end Loop;
    end;

    function IsValid(pBan BanDef,pX pls_Integer,pY pls_Integer,N pls_Integer) return boolean is
    squX pls_Integer;squY pls_Integer;
    begin
        for X in 1..9 Loop
            if (pBan(X)(pY) = N) then return false; end if;
        end Loop;
        for Y in 1..9 Loop
            if (pBan(pX)(Y) = N) then return false; end if;
        end Loop;

        squX := case when pX in(1,2,3) then 1
                     when pX in(4,5,6) then 4
                     else 7 end;
        squY := case when pY in(1,2,3) then 1
                     when pY in(4,5,6) then 4
                     else 7 end;

        for X in squX..squX+2 Loop
            for Y in squY..squY+2 Loop
                if (pBan(X)(Y) = N) then return false; end if;
            end Loop;
        end Loop;
        return true;
    end;

begin
    push(Ban);

    while (IsEmpty = false) loop
        Ban := pop();

        targetX := 1; targetY := 1;
        while (targetX != 10) loop
            exit when Ban(targetX)(targetY) = 0;
            targetY := targetY+1;
            if (targetY = 10) then
                targetX := targetX+1;
                targetY := 1;
            end if;
        end Loop;

        if (targetX = 10) then
            DBMS_Output.Put_Line('Answer');
            printBan(Ban);
        else
            for N in 1..9 Loop
                if (IsValid(Ban, targetX, targetY, N)) then
                    Ban(targetX)(targetY) := N;
                    push(Ban);
                end if;
            end Loop;
        end if;
    end Loop;
end;
/

実行結果

Answer
-----------------
6,8,4,7,9,1,2,5,3,
5,7,2,3,4,8,9,6,1,
9,3,1,5,2,6,8,7,4,
8,2,3,1,7,4,5,9,6,
4,9,6,2,8,5,1,3,7,
7,1,5,9,6,3,4,2,8,
2,4,8,6,3,9,7,1,5,
1,6,7,4,5,2,3,8,9,
3,5,9,8,1,7,6,4,2,

解説

スタックなデータ構造を配列で実装してます。
スタック (stack)の資料
待ち行列，キュー(queue)の資料

C#のサンプル集 8-8 数独
Javaアルゴリズムパズル 3-7 数独
PostgreSQLパズル 再帰with句10 数独を解く
DB2 SQLパズル 再帰with句10 数独を解く