才知道还有16*16的数独

〇〇

〇〇 发表于 2016-9-18 10:59
D:\>cl dlx_9a.cpp   /MD
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for ...

16*16也没有压力
D:\>cl dlx_16.cpp  /MD
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.

dlx_16.cpp
Microsoft (R) Incremental Linker Version 10.00.40219.01
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:dlx_16.exe
dlx_16.obj

D:\lutao\1>dlx_16
--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-
FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK

Time:118 Ms

newkid

〇〇 发表于 2016-9-18 08:02
就用你以前的高精度加法库,
我怎么用bitand的比instr还慢？
http://www.itpub.net/forum.php?mod=redir ...

你有这闲情逸致，就用PLSQL PROFILER跟踪一下时间花在哪里。

〇〇

newkid 发表于 2016-9-19 23:19
你有这闲情逸致，就用PLSQL PROFILER跟踪一下时间花在哪里。

UNIT_NAME       LINE# TOTAL_TIME TOTAL_OCCUR   MIN_TIME   MAX_TIME TEXT
---------- ---------- ---------- ----------- ---------- ---------- ----------------------------------------------------------------------
<anonymous         15      36968           1      36968      36968
>

<anonymous         18      12989           1      12989      12989
>

<anonymous         25       6994           1       6994       6994
>

SD3B               11   20518644       29695        999      25978 i:=instr(a,'0');
SD3B               12    4723005       29695          0       9991 if (i=0) then
SD3B               13       7993           1       7993       7993 dbms_output.put_line(a);
SD3B               14          0           1          0          0 return;
SD3B               16    4056568       29694        999       2997 e:=0;
SD3B               17   30199455       29694        999      68941 r:=floor((i-1)/9)+1;
SD3B               18   25352555       29694        999      32972 c:=mod(i-1,9)+1;
SD3B               19   26668442       29694        999      31972 r0:=floor((i-1)/27)*3+1;
SD3B               20   25014841       29694        999      31972 c0:=floor(mod(i-1,9)/3)*3+1;
SD3B               22   46396755      296940        999      48958 for j in 1..9 loop
SD3B               23   97219767      267246          0      46960 n:=(r-1)*9+j;
SD3B               24  324643401      267246        999      89923 if bitand(e,power(2,substr(a,n,1)))=0 then
SD3B               25   60964433      213484          0      39966    e:=e+power(2,substr(a,n,1));
SD3B               29   39502586      267246          0      56951 for j in 1..9 loop
SD3B               30  134968837      267246          0     290754 n:=(j-1)*9+c;
SD3B               31  333941536      267246        999      76934 if bitand(e,power(2,substr(a,n,1)))=0 then
SD3B               32   13470605       45441          0      30973    e:=e+power(2,substr(a,n,1));
SD3B               36   38668292      267246          0      31972 for j in 1..9 loop
SD3B               37  495973482      267246        999      61947 n:=(r0+floor((j-1)/3)-1)*9+c0+mod(j-1,3);
SD3B               38  355049682      267246        999     678426 if bitand(e,power(2,substr(a,n,1)))=0 then
SD3B               39    2554838        8321          0       4995    e:=e+power(2,substr(a,n,1));
SD3B               43   38335574      267246          0     163861 for m in 1 ..9 loop
SD3B               44  277423342      267246        999      78933 if bitand(e,power(2,m))=0 then
SD3B               47   43070568       29694        999      55952 sd3b(substr(a,1,i-1)||m||substr(a,i+1));
SD3B               50    6107833       29694       3996       6994 end;

〇〇

〇〇 发表于 2016-9-20 09:34
UNIT_NAME       LINE# TOTAL_TIME TOTAL_OCCUR   MIN_TIME   MAX_TIME TEXT
---------- ---------- --- ...

时间就花在bitand上
UNIT_NAME         LINE# TOTAL_TIME TOTAL_OCCUR   MIN_TIME   MAX_TIME TEXT
------------ ---------- ---------- ----------- ---------- ---------- ----------------------------------------------------------------------
<anonymous>          15      35995           1      35995      35995
<anonymous>          18      24997           1      24997      24997
<anonymous>          25       6999           1       6999       6999
SD3                  11   20412568       29695          0      39995 i:=instr(a,'0');
SD3                  12    4465468       29695        999      19997 if (i=0) then
SD3                  13      77990           1      77990      77990 dbms_output.put_line(a);
SD3                  14        999           1        999        999 return;
SD3                  16    5447351       29694          0      22997 e:='a';
SD3                  17   30522364       29694        999      53993 r:=floor((i-1)/9)+1;
SD3                  18   25750933       29694        999      42994 c:=mod(i-1,9)+1;
SD3                  19   26454849       29694        999      37995 r0:=floor((i-1)/27)*3+1;
SD3                  20   24742053       29694        999      37995 c0:=floor(mod(i-1,9)/3)*3+1;
SD3                  22   44285725      296940          0      30996 for j in 1..9 loop
SD3                  23  100854988      267246        999      62992 n:=(r-1)*9+j;
SD3                  24  245700737      267246          0     173979 if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
SD3                  25   48610210      183790          0      56993    e:=e||substr(a,n,1);
SD3                  29   38848373      267246          0      28996 for j in 1..9 loop
SD3                  30  133542095      267246          0      70991 n:=(j-1)*9+c;
SD3                  31  208779134      267246        999      73991 if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
SD3                  32   12316533       45441        999      36995    e:=e||substr(a,n,1);
SD3                  36   38854372      267246          0      34995 for j in 1..9 loop
SD3                  37  489213736      267246        999     909891 n:=(r0+floor((j-1)/3)-1)*9+c0+mod(j-1,3);
SD3                  38  206633390      267246        999     178978 if instr(e,substr(a,n,1))=0 and substr(a,n,1)<>0 then
SD3                  39    2444708        8321          0       4999    e:=e||substr(a,n,1);
SD3                  43   41404068      267246          0      34995 for m in 1 ..9 loop
SD3                  44  163356544      267246        999     486942 if instr(e,m)=0 then
SD3                  46   39837255       29694        999      99988 sd3(substr(a,1,i-1)||m||substr(a,i+1));
SD3                  49    6229258       29694       3999      36995 end;

〇〇

〇〇 发表于 2016-9-20 09:39
时间就花在bitand上
UNIT_NAME         LINE# TOTAL_TIME TOTAL_OCCUR   MIN_TIME   MAX_TIME TEXT
-- ...

增加一个条件，快了一点
------------ ---------- ---------- ----------- ---------- ---------- ----------------------------------------------------------------------
<anonymous>          15      38997           1      38997      38997
<anonymous>          18      21998           1      21998      21998
<anonymous>          25       6999           1       6999       6999
SD3B1                11   22225488       29695        999      23998 i:=instr(a,'0');
SD3B1                12    4801673       29695          0      17998 if (i=0) then
SD3B1                13      96993           1      96993      96993 dbms_output.put_line(a);
SD3B1                14          0           1          0          0 return;
SD3B1                16    4314706       29694        999       4999 e:=0;
SD3B1                17   30838902       29694        999      24998 r:=floor((i-1)/9)+1;
SD3B1                18   25320277       29694        999      23998 c:=mod(i-1,9)+1;
SD3B1                19   26936167       29694        999      21998 r0:=floor((i-1)/27)*3+1;
SD3B1                20   25230283       29694        999      23998 c0:=floor(mod(i-1,9)/3)*3+1;
SD3B1                22   45839881      296940          0      54996 for j in 1..9 loop
SD3B1                23   98367308      267246          0      29997 n:=(r-1)*9+j;
SD3B1                24  298883668      267246        999     114992 if substr(a,n,1)>0 and bitand(e,power(2,substr(a,n,1)))=0 then
SD3B1                25   55550221      183790          0      23998    e:=e+power(2,substr(a,n,1));
SD3B1                29   40097272      267246          0      30997 for j in 1..9 loop
SD3B1                30  135039813      267246          0     489966 n:=(j-1)*9+c;
SD3B1                31  272523461      267246        999     194986 if substr(a,n,1)>0 and bitand(e,power(2,substr(a,n,1)))=0 then
SD3B1                32   14270029       45441          0      14998    e:=e+power(2,substr(a,n,1));
SD3B1                36   39582307      267246          0      37997 for j in 1..9 loop
SD3B1                37  492958466      267246        999     122991 n:=(r0+floor((j-1)/3)-1)*9+c0+mod(j-1,3);
SD3B1                38  276345201      267246        999      66995 if substr(a,n,1)>0 and bitand(e,power(2,substr(a,n,1)))=0 then
SD3B1                39    2473831        8321        999      18998    e:=e+power(2,substr(a,n,1));
SD3B1                43   40046275      267246          0      26998 for m in 1 ..9 loop
SD3B1                44  281502850      267246        999      56996 if bitand(e,power(2,m))=0 then
SD3B1                47   43579035       29694        999     734950 sd3b1(substr(a,1,i-1)||m||substr(a,i+1));
SD3B1                50    6054588       29694       4999       6999 end;

已选择28行。

已用时间:  00: 00: 00.11
SQL> exec sd3b1('200370009009200007001004002050000800008000900006000040900100500800007600400089001');
284375169639218457571964382152496873348752916796831245967143528813527694425689731

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.15

〇〇

〇〇 发表于 2016-9-20 09:47
增加一个条件，快了一点
------------ ---------- ---------- ----------- ---------- ---------- ----- ...

知道了,原来是power2慢，
create or replace procedure sd3b3(a in varchar)
is
type int_varray is varray(10) of int;
pow2 int_varray:=int_varray();
procedure sd3b3_inner(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 substr(a,n,1)>0 and bitand(e,pow2(substr(a,n,1)))=0 then
   e:=e+pow2(substr(a,n,1));
end if;
end loop;
--same col
for j in 1..9 loop
n:=(j-1)*9+c;
if substr(a,n,1)>0 and bitand(e,pow2(substr(a,n,1)))=0 then
   e:=e+pow2(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 substr(a,n,1)>0 and bitand(e,pow2(substr(a,n,1)))=0 then
   e:=e+pow2(substr(a,n,1));
end if;
end loop;

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

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

begin
pow2.extend(10);
for i in 1..10 loop
pow2(i):=power(2,i);
end loop;
sd3b3_inner(a);
end;
/

exec sd3b3('200370009009200007001004002050000800008000900006000040900100500800007600400089001');

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.02

〇〇

newkid 发表于 2016-9-17 20:33
我没看那个算法，我是说原来的算法扩容并不难。
我自己有个SQL写法，用到了BITAND，原来81位二进制可以用N ...

这里有个中文的
http://www.cnblogs.com/grenet/p/3163550.html

yulihua49

知道纳粹的ENIGMA密码机吗？那是一个26*17576的数独，全部用26个字母填充。图灵的玩具，后来简化成9*9的数字格，才成了大家的玩具。

newkid

yulihua49 发表于 2016-9-24 22:26
知道纳粹的ENIGMA密码机吗？那是一个26*17576的数独，全部用26个字母填充。图灵的玩具，后来简化成9*9的数 ...

厉害，想不到你还研究这个。
http://m.blog.chinaunix.net/uid-8804348-id-2013150.html

〇〇

我想起来了,是说ENIGMA密码的每个字母必须和原文不同