用PLSQL解数独(SUDOKU)

〇〇 · 发表于 2016-9-22 14:45

〇〇发表于 2016-9-22 12:29
create or replace procedure sd4(a in varchar)
is
type int_varray is varray(20) of int;

create or replace procedure sd5(a in varchar)
is
type int_varray3 is varray(81) of varchar(10);
ex int_varray3:=int_varray3();
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);
ex.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
if substr(a,j,1)='0' then
   sd(i)(k):=j;
   k:=k+1;
elsif instr(ex(i),substr(a,j,1))=0 or instr(ex(i),substr(a,j,1)) is null then
   ex(i):=ex(i)||substr(a,j,1);
end if;
end if;
end loop;
dbms_output.put_line('');
end loop;

end;

procedure sd5_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'||ex(i);
--lookup in 20 neibour

for j in 1..20 loop
n:=sd(i)(j);
if n is null then
  exit;
end if;
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));
sd5_inner(substr(a,1,i-1)||m||substr(a,i+1));
end if;
end loop;
end;

begin

init;
sd5_inner(a);
end;
/

〇〇 · 发表于 2016-9-22 14:49

〇〇发表于 2016-9-22 14:45
create or replace procedure sd5(a in varchar)
is
type int_varray3 is varray(81) of varchar(10);
...

SQL> exec sd5('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
812753649943682175675491283154237896369845721287169534521974368438526917796318452

PL/SQL 过程已成功完成。

已用时间:  00: 00: 17.02
SQL> exec sd4('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
812753649943682175675491283154237896369845721287169534521974368438526917796318452

PL/SQL 过程已成功完成。

已用时间:  00: 00: 21.41
SQL> exec sd3('800000000003600000070090200050007000000045700000100030001000068008500010090000400')
812753649943682175675491283154237896369845721287169534521974368438526917796318452

PL/SQL 过程已成功完成。

已用时间:  00: 00: 40.65

〇〇 · 发表于 2016-9-23 08:46

〇〇发表于 2016-9-22 14:49
SQL> exec sd5('800000000003600000070090200050007000000045700000100030001000068008500010090000400') ...

90楼注释改进思路1，把原始布局中的未知格子的邻居（同行、同列、同宫）一次性找出来，每次调用函数只要列举这个格子的邻居即可。每个格子都有20个邻居。
91楼注释改进思路2，上述20个邻居中，有些是已知的，有些是未知的。已知的不会变化，所以只要记得它们包含的数字，未知的每次尝试不同的数字时会变化，需要遍历。

〇〇 · 发表于 2016-9-23 09:03

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

每个空格用候选数m来遍历的好处是，只要有一个邻居用过m就返回，不用把27个格都列举

〇〇 · 发表于 2016-9-23 12:58

〇〇发表于 2016-9-23 09:03
每个空格用候选数m来遍历的好处是，只要有一个邻居用过m就返回，不用把27个格都列举

结合91楼,目前蛮力法中最快
set serverout on
create or replace procedure p_sd5
is
s varchar(81);
isok boolean:=false;
type int_varray is varray(81) of int;
sd int_varray:=int_varray();

type int_varray3 is varray(81) of varchar(10);
ex int_varray3:=int_varray3();
-- fill exclude
procedure init2
is
k int;
begin
--find each one's 20 neibour
--sd.extend(81);
ex.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
if sd(j)='0' then
   --sd(i)(k):=j;
   k:=k+1;
elsif instr(ex(i),sd(j))=0 or instr(ex(i),sd(j)) is null then
   ex(i):=ex(i)||sd(j);
end if;
end if;
end loop;
dbms_output.put_line('');
end loop;

end;

--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;
      if instr(ex(k+one),m)>0 then
         mm:=false;
      else
         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;
         end if;
         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;
init2;
force(0);
end;
/

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

PL/SQL 过程已成功完成。

已用时间:  00: 00: 03.22

〇〇 · 发表于 2016-9-28 18:35

SQL> exec sudoku3('000000010400000000020000000000050407008000300001090000300400200050100000000806000')

PL/SQL 过程已成功完成。

已用时间: 00: 00: 09.23

〇〇 · 发表于 2016-9-29 14:20

idoTen 发表于 2008-10-23 10:41
膜拜下, 我sudoku的过关记录都要5分钟以上了

我easy和middle都要13分钟

〇〇 · 发表于 2016-9-29 14:20

H19-RecBacktrackExamples.pdf (174.65 KB, 下载次数: 20)

The.Algorithm.Design.Manual,.2ed),.Skiena.pdf (3.13 MB, 下载次数: 24)

renfengjun8 · 发表于 2016-9-29 16:46

我这每天拿着人脑算，还得标记一下。

〇〇 · 发表于 2016-9-29 16:59

renfengjun8 发表于 2016-9-29 16:46
我这每天拿着人脑算，还得标记一下。

人眼容易遗漏,还有一些固定局面要反应快

用PLSQL解数独(SUDOKU)

浏览过的版块