用SQL或PL/SQL求解数独，替三思发帖。

wxy0327 · 发表于 2021-7-22 16:47

本帖最后由 wxy0327 于 2021-7-22 16:49 编辑

newkid 发表于 2008-10-18 03:18
[ 本帖最后由 newkid 于 2008-10-18 05:24 编辑 ]

我用https://baike.baidu.com/item/%E4 ... 13848819?fr=aladdin 测试单机 120毫秒，已经是我所看到最快的DB解决方案了。大神能改成postgresql的么？

newkid · 发表于 2021-7-22 23:32

wxy0327 发表于 2021-7-22 16:47
我用https://baike.baidu.com/item/%E4 ... 13848819?fr=aladdin 测试单机 120毫秒，已经是我所看 ...

postgresql是最接近oracle的数据库，实现了大部分PL/SQL的功能，所以肯定是没问题的。你试过了没有？如果不行是卡在哪里？
我手头没有装pg, 没法测试，要不你可以请OO帮忙测试。

jihuyao · 发表于 2021-7-23 13:29

数独 has been overlooked too long for its role in logical thinking and programming learning. Combined with SQL, it can be an easy topic for 3rd grader to start learning some logical flow and simple programming. For example, how many valid settings to put 1-9 into the 9x9 grid? In SQL, it is simply, select Xi, ... from Ti, ... where Xi in (1,2,3,4,5,6,7,8,9) ... and Xi<>Xi ... ; Note 1<=i,j<=81 and i,j are peer pairs. To further solve a given problem, add detailed given conditions in the where clause as much as possible, eg, X1=5,...X81=2. Of course it can provide many challenges as one wish with growing age.

newkid · 发表于 2021-7-23 21:20

jihuyao 发表于 2021-7-23 13:29
数独 has been overlooked too long for its role in logical thinking and programming learning. Combin ...

如果不用PL/SQL，单纯用SQL来实现还是有一定挑战的。荷兰有位老兄提供了一种非常简洁的写法，我自己写了个比较复杂的SQL, 但是我的写法效率比他高。

wxy0327 · 发表于 2021-7-26 17:02

本帖最后由 wxy0327 于 2021-7-26 18:19 编辑

newkid 发表于 2021-7-22 23:32
postgresql是最接近oracle的数据库，实现了大部分PL/SQL的功能，所以肯定是没问题的。你试过了没有？如果不 ...

已改写，但比Oracle慢了4倍多，900毫秒左右

DO $DECLARE
i int;
j int;
k int;
s _varchar(10);
used_c int[][]:=array_fill(0,array[9,9]); --- in this column whether the number has been used
used_r int[][]:=array_fill(0,array[9,9]); --- in this row whether the number has been used
used_a int[][]:=array_fill(0,array[9,9]); --- in this area whether the number has been used
area int[][]:=array_fill(0,array[9,9]); ---- mapping from row, column to area
v_cnt int :=0;
slot_value int[][]:=array_fill(0,array[100,100]);
slot_r int[];
slot_c int[];
v_cnt2 int :=0;
v_idx int;
slot_value_idx int[]=array_fill(1,array[60]);
BEGIN
s[1]:= '8 ';
s[2]:= ' 36 ';
s[3]:= ' 7 9 2 ';
s[4]:= ' 5 7 ';
s[5]:= ' 457 ';
s[6]:= ' 1 3 ';
s[7]:= ' 1 68';
s[8]:= ' 85 1 ';
s[9]:= ' 9 4 ';
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
area[i][j] := (CEIL(i::numeric/3::numeric)-1)*3 + CEIL(j::numeric/3::numeric);
--raise notice '%.%',i,j;
--raise notice '%',area[i][j];
END LOOP;
END LOOP;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
k := (case when TRIM(SUBSTRing(s[i],j,1))='' then '0' else TRIM(SUBSTRing(s[i],j,1)) end)::int;
IF k>0 THEN
used_c[j][k] :=1;
used_r[i][k] :=1;
used_a[area[i][j]][k] :=1;
--raise notice 'aaaaaaaaaa';
END IF;
END LOOP;
END LOOP;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
IF SUBSTRing(s[i],j,1)=' ' THEN
v_cnt := v_cnt+1;
v_cnt2 :=0;
FOR k IN 1..9 LOOP
IF used_c[j][k] = 0 AND used_r[i][k] = 0 AND used_a[area[i][j]][k] = 0 THEN ---- possible value found for this slot
v_cnt2 := v_cnt2 +1;
slot_value[v_cnt][v_cnt2] := k;
--raise info 'slot_value[v_cnt][v_cnt2]: %',slot_value[v_cnt][v_cnt2];
END IF;
END LOOP;
IF v_cnt2 = 0 THEN
RAISE EXCEPTION '-20001,invalid sudoku at %,%',i,j;
END IF;
IF v_cnt2 = 1 THEN ---- there's only one value for this slot, it's the answer
k := slot_value[v_cnt][1];
used_c[j][k] :=1;
used_r[i][k] :=1;
used_a[area[i][j]][k] :=1;
v_cnt := v_cnt - 1;
s[i] := SUBSTRing(s[i],1,j-1) ||k|| SUBSTRing(s[i],j+1);
--raise notice 'bbbbbbbbbb';
ELSE
slot_r[v_cnt] := i; ---- position of this slot
slot_c[v_cnt] := j;
END IF;
END IF;
END LOOP;
END LOOP;
--raise notice '00000000000--%',s;
--raise notice '-----------------';
---- initialize the value indexes of slots
/*v_idx := 1;
WHILE slot_value[v_idx][1] <>0 LOOP
slot_value_idx[v_idx] := 1;
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value[v_idx].FIRST);
v_idx := v_idx+1;
raise notice '111--%---%',v_idx,slot_value_idx[v_idx];
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value.NEXT[v_idx]);
END LOOP;*/
--raise notice '111--%',slot_value_idx[60];
v_idx := slot_value[1][1];
WHILE slot_value[v_idx][1] <>0 LOOP
--indx2:=1;
--raise notice '----------';
WHILE slot_value_idx[v_idx]<>0 LOOP ---- try all values for this slot
--raise notice '+++++++%',slot_value_idx[v_idx];
i := slot_r[v_idx];
j := slot_c[v_idx];
k := slot_value[v_idx][slot_value_idx[v_idx]];
--raise notice 'v_idx : % i : % j : % k : %',v_idx,i,j,k;
--raise notice 'v_idx : % used_c[j][k] : % uused_r[i][k] : % used_a[area[i][j]][k] : %',v_idx,used_c[j][k],used_r[i][k],used_a[area[i][j]][k];
IF used_c[j][k] = 0 AND used_r[i][k] = 0 AND used_a[area[i][j]][k] = 0 THEN ---- possible value found for this slot
--raise notice 'mmmmmmmmmm';
used_c[j][k] := 1;
used_r[i][k] := 1;
used_a[area[i][j]][k] :=1;
EXIT;
END IF;
/*if slot_value[indx2][1] =0 and indx2>1 then
EXIT;
end if;*/
--indx2:=indx2+1;
slot_value_idx[v_idx] := case when slot_value[v_idx][slot_value_idx[v_idx]+1] = 0 then 0 else slot_value_idx[v_idx]+1 end;
--raise notice '0000--%,%,%',v_idx,slot_value_idx[v_idx],case when slot_value[v_idx][slot_value_idx[v_idx]+1] = 0 then 0 else slot_value_idx[v_idx]+1 end;
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value_idx[v_idx]||','||slot_value[v_idx].NEXT(slot_value_idx[v_idx]));
END LOOP;
--raise notice '0000000--%',v_idx;
IF slot_value_idx[v_idx]=0 THEN ---- all values tried but none is the answer
--raise notice '-----------------';
slot_value_idx[v_idx] := slot_value[1][1]; --- reset the index of this slot
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value[v_idx].FIRST);
v_idx := v_idx-1; --- go back and release the last slot
--raise notice '111111--%',v_idx;
IF slot_value[v_idx][1] =0 THEN ----- no anwer found
raise notice 'No Answer Found!';
EXIT;
END IF;
i := slot_r[v_idx];
j := slot_c[v_idx];
k := slot_value[v_idx][slot_value_idx[v_idx]];
used_c[j][k] := 0;
used_r[i][k] := 0;
used_a[area[i][j]][k] :=0;
--indx2:=indx2+1;
slot_value_idx[v_idx] := case when slot_value[v_idx][slot_value_idx[v_idx]+1] = 0 then 0 else slot_value_idx[v_idx]+1 end;
--raise notice '1111--%,%,%',v_idx,slot_value_idx[v_idx],case when slot_value[v_idx][slot_value_idx[v_idx]+1] = 0 then 0 else slot_value_idx[v_idx]+1 end;
ELSE
--raise notice '-----------------';
--if v_idx+1 = 61 then
--v_idx:=0;
--else
v_idx := v_idx+1;
--end if;
--raise notice '222222--%',v_idx;
IF slot_value[v_idx][1] =0 THEN ----- all slots tried and found an answer
v_idx := slot_value[1][1];
--raise notice '333333--%',v_idx;
WHILE slot_value[v_idx][1] <>0 and v_idx<>61 LOOP
i := slot_r[v_idx];
j := slot_c[v_idx];
k := slot_value[v_idx][slot_value_idx[v_idx]];
s[i] := SUBSTRing(s[i],1,j-1) || k || SUBSTRing(s[i],j+1);
v_idx := v_idx+1;
--raise notice 'sssssssssssss--%',s[i];
--raise notice '4444444--%',v_idx;
--raise notice 'slot_value_idx[v_idx] : %',slot_value_idx[v_idx];
--raise notice 'v_idx : % i : % j : % k : %',v_idx,i,j,k;
END LOOP;
raise notice 'Answer Found:';
FOR i IN 1..9 LOOP
raise notice '%',s[i];
END LOOP;
EXIT;
END IF;
END IF;
--raise notice '333--%',v_idx;
END LOOP;
END$;

复制代码

newkid · 发表于 2021-7-26 22:00

和PL/SQL几乎一摸一样嘛！
PL/SQL本身的性能不能和C，JAVA相比，它存在的意义不是用来做算法的，而是一种专门执行SQL的事务语言，类似SQL的粘合剂。

jihuyao · 发表于 2021-7-27 16:45

If remember correctly, that sql used recursive and later Oracle wrote an article to modify it in great details to make it harder to catch the basic logic. The plain sql way may be too long in syntax but the logic is straight and easy too understand. However, I would suggest to work on 4X4 grids (so Xi in 1,2,3,4) first. Then sql will be much shortened but the logic is completely the same. As 5th grader now I would add some skills like view, dynamic sql, hint, row number=1(for any given problem), etc to make coding easier and performance better. In fact, for hard problems with chain link, there is no easy logical flow in procedure way (eg nested trial and error, brutal force, recursive function with changing data source arrays. So the basic sql can be very handy and effective to the last step after procedure method identifies as many array elements as possible using well defined logics. So instead of teaching “hello world”, teach how to count 2!, 4!, 9!, and their conditional combinations in standard SQL would definitely boost 3rd graders confidence for future programming learning in other languages.

newkid · 发表于 2021-7-27 21:25

你说的” make it harder to catch the basic logic“是啥意思？改得比原来更难懂了？请给个链接。
你给自己的定位到底是五年级学生，还是编程老师？动手玩玩，把代码贴出来，比讲一堆原理更有趣。

newkid · 发表于 2021-7-27 23:24

纯SQL版本在这里：
http://www.itpub.net/thread-1478962-1-1.html

jihuyao · 发表于 2021-7-28 02:29

Like bear picking corns I am less organized than 5th grader. I almost make no links in most topics. But I do posted only one in sudoku website without marking link. Let me try to find that one sometime later. I do played a bunch of things all messed up together (but has not touched for quit long). If someone wants further discussion maybe I can manage to sort something useful out.

[SQL] 用SQL或PL/SQL求解数独，替三思发帖。