用PLSQL解数独(SUDOKU)

〇〇

〇〇 发表于 2016-9-16 09:18
一个易懂的python版本
https://pythontips.com/2013/09/01/sudoku-solver-in-python/
原文在3.5上报错,改 ...

python 3 /返回浮点数,//返回整数,要把附件中/全替换为//,否则算错

〇〇

〇〇 发表于 2016-9-16 11:22
python 3 /返回浮点数,//返回整数,要把附件中/全替换为//,否则算错

效率比较差
create or replace procedure sd2(a in varchar)
as
i int;
e varchar(10);
begin
i:=instr(a,'0');
if (i=0) then
dbms_output.put_line(a);
return;
end if;
e:='a';
for j in 1..81 loop
if (floor((i-1)/9) = floor((j-1)/9)) or
(mod(i-j, 9) = 0) or
(floor((i-1)/27) = floor((j-1)/27) and floor(mod(i-1,9)/3) = floor(mod(j-1,9)/3)) then
if instr(e,substr(a,j,1))=0 and substr(a,j,1)<>0 then
   e:=e||substr(a,j,1);
end if;
end if;
end loop;
for m in 1 ..9 loop
if instr(e,m)=0 then
sd2(substr(a,1,i-1)||m||substr(a,i+1));
end if;
end loop;
end;
/

SQL> exec sd2('200370009009200007001004002050000800008000900006000040900100500800007600400089001')
284375169639218457571964382152496873348752916796831245967143528813527694425689731

PL/SQL 过程已成功完成。

已用时间:  00: 00: 06.27

〇〇

〇〇 发表于 2016-9-16 15:53
效率比较差
create or replace procedure sd2(a in varchar)
as

把第2步的81次循环改为27次,快了点
create or replace procedure sd3(a in varchar)
as
i int;
r int;
c int;
r0 int;
c0 int;
n int;
e varchar(10);
begin
i:=instr(a,'0');
if (i=0) then
dbms_output.put_line(a);
return;
end if;
e:='a';
r:=floor((i-1)/9)+1;
c:=mod(i-1,9)+1;
r0:=floor((i-1)/27)*3+1;
c0:=floor(mod(i-1,9)/3)*3+1;
--same row
for j in 1..9 loop
n:=(r-1)*9+j;
if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
   e:=e||substr(a,n,1);
end if;
end loop;
--same col
for j in 1..9 loop
n:=(j-1)*9+c;
if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
   e:=e||substr(a,n,1);
end if;
end loop;
--same blk
for j in 1..9 loop
n:=(r0+floor((j-1)/3)-1)*9+c0+mod(j-1,3);
if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
   e:=e||substr(a,n,1);
end if;
end loop;

for m in 1 ..9 loop
if instr(e,m)=0 then
--dbms_output.put_line(substr(a,1,i-1)||'('||m||')'||substr(a,i+1));
sd3(substr(a,1,i-1)||m||substr(a,i+1));
end if;
end loop;
end;
/

exec sd3('200370009009200007001004002050000800008000900006000040900100500800007600400089001')

284375169639218457571964382152496873348752916796831245967143528813527694425689731

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.07

〇〇

〇〇 发表于 2016-9-16 19:45
把第2步的81次循环改为27次,快了点
create or replace procedure sd3(a in varchar)
as

奇怪,改为bitand反而慢了
create or replace procedure sd3b(a in varchar)
as
i int;
r int;
c int;
r0 int;
c0 int;
n int;
e int;
begin
i:=instr(a,'0');
if (i=0) then
dbms_output.put_line(a);
return;
end if;
e:=0;
r:=floor((i-1)/9)+1;
c:=mod(i-1,9)+1;
r0:=floor((i-1)/27)*3+1;
c0:=floor(mod(i-1,9)/3)*3+1;
--same row
for j in 1..9 loop
n:=(r-1)*9+j;
if bitand(e,power(2,substr(a,n,1)))=0 then
   e:=e+power(2,substr(a,n,1));
end if;
end loop;
--same col
for j in 1..9 loop
n:=(j-1)*9+c;
if bitand(e,power(2,substr(a,n,1)))=0 then
   e:=e+power(2,substr(a,n,1));
end if;
end loop;
--same blk
for j in 1..9 loop
n:=(r0+floor((j-1)/3)-1)*9+c0+mod(j-1,3);
if bitand(e,power(2,substr(a,n,1)))=0 then
   e:=e+power(2,substr(a,n,1));
end if;
end loop;

for m in 1 ..9 loop
if bitand(e,power(2,m))=0 then

--dbms_output.put_line(substr(a,1,i-1)||'('||m||')'||substr(a,i+1));
sd3b(substr(a,1,i-1)||m||substr(a,i+1));
end if;
end loop;
end;
/

exec sd3b('200370009009200007001004002050000800008000900006000040900100500800007600400089001')
284375169639218457571964382152496873348752916796831245967143528813527694425689731

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.49

〇〇

效率好点的版本
set serverout on
create or replace procedure p_sd
is
s varchar(81);
isok boolean:=false;
type int_varray is varray(81) of int;
sd int_varray:=int_varray();
--init varray
procedure init
is
begin
for i in 1..81 loop
sd(i):=ascii(substr(s,i,1))-ascii('0');
end loop;
end;
--show result
procedure show
is
begin
if isok then
dbms_output.put_line('solved');
else
dbms_output.put_line('failed');
end if;
/*
for i in 1..9 loop
dbms_output.put_line(substr(sd,i*9-8,9));
end loop;
*/
for i in 1..81 loop
dbms_output.put(chr(sd(i)+ascii('0')));
if mod(i,9)=0 then
dbms_output.put_line('');
end if;
end loop;
end;
--solve
procedure force(k int )
is
mm boolean;
one int:=1;
begin
    if (isok) then
        return;
    end if;
    if (sd(k+one)=0) then
        for m in 1..9 loop
            mm := true;
            for n in 0..8 loop
                if (m = sd(floor(k / 27) * 27 + floor(mod(k , 9) / 3) * 3 + n + floor(n / 3) * 6 + one) or m = sd(9 * n + mod(k , 9)+ one) or m = sd(floor(k / 9) * 9 + n+one)) then
                    mm := false;
                    exit;
                end if;
            end loop;
            if (mm) then
                sd(k+one) := m;
                if (k = 80) then
                    isok := true;
                    show();
                    return;
                end if;
                force(k + 1);
            end if;
        end loop;
        sd(k+one) := 0;
    else
        if (k = 80) then
            isok := true;
            show();
            return;
        end if;
        force(k + 1);
    end if;
end;

begin
isok:=false;
s:='800000000003600000070090200050007000000045700000100030001000068008500010090000400';
sd.extend(81);
init;
force(0);
end;
/



SQL> exec p_sd
solved
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

PL/SQL 过程已成功完成。

已用时间:  00: 00: 05.27

regonly1

牛

〇〇

〇〇 发表于 2016-9-18 15:37
效率好点的版本
set serverout on
create or replace procedure p_sd

把变量s改为参数
SQL> exec p_sd(800000000003600000070090200050007000000045700000100030001000068008500010090000400)
solved
812345679
493672158
576198234
154237896
237869415
689451327
325784961
741926583
968513742

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.03
SQL> exec p_sd(200370009009200007001004002050000800008000900006000040900100500800007600400089001)
solved
245371689
369258147
781694352
152437896
438169275
697582413
513746928
826915734
974823561

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01

〇〇

〇〇 发表于 2016-9-20 12:41
把变量s改为参数
SQL> exec p_sd(800000000003600000070090200050007000000045700000100030001000068008 ...

答案明显是错的,因为漏打''
下面是对的
SQL> exec p_sd('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
solved
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

PL/SQL 过程已成功完成。

已用时间:  00: 00: 05.29

〇〇

SudokuSolver.pdf (136.57 KB, 下载次数: 22)

2016-9-20 15:41 上传

点击文件名下载附件

mathematica

〇〇

〇〇 发表于 2016-9-16 19:45
把第2步的81次循环改为27次,快了点
create or replace procedure sd3(a in varchar)
as

create or replace procedure sd4(a in varchar)
is
type int_varray is varray(20) of int;
type int_varray2 is varray(81) of int_varray;
sd int_varray2:=int_varray2();

procedure init
is
k int;
begin
--find each one's 20 neibour
sd.extend(81);
for i in 1..81 loop
sd(i):=int_varray();
sd(i).extend(20);
k:=1;
for j in 1..81 loop
if i<>j and  ((floor((i-1)/9) = floor((j-1)/9)) or
   (mod(i-j, 9) = 0) or
   (floor((i-1)/27) = floor((j-1)/27) and floor(mod(i-1,9)/3) = floor(mod(j-1,9)/3))) then
     sd(i)(k):=j;
     k:=k+1;
end if;
end loop;
dbms_output.put_line('');
end loop;

end;


procedure sd4_inner(a in varchar)
as
i int;
n int;
e varchar(10);


begin
i:=instr(a,'0');
if (i=0) then
dbms_output.put_line(a);
return;
end if;
e:='a';
--lookup in 20   neibour  

for j in 1..20 loop
n:=sd(i)(j);
if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
   e:=e||substr(a,n,1);
end if;
end loop;


for m in 1 ..9 loop
if instr(e,m)=0 then
--dbms_output.put_line(substr(a,1,i-1)||'('||m||')'||substr(a,i+1));
sd4_inner(substr(a,1,i-1)||m||substr(a,i+1));
end if;
end loop;
end;

begin

init;
sd4_inner(a);
end;
/