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

nyfor

都在研究算法了啊...

newkid

这种问题是很有趣的，因为它起点不高但要做好不容易。
最直观的想法就是用1-9去试每个空格了，但这样的效率肯定成问题。我现在的想法是加些简单推理排除一些，这样每个空就不必9个数字都去试了。

newkid

1. 
   
2. 
   
3. 第一位SQL牛人（其实他的MODEL已经和传统SQL天差地别了）的测试用例，他花了40秒，我的PL/SQL用时 1.5 秒。
   
4. 第二位用SQLSERVER存储过程的，他用了一个号称史上最难的例子，花了5分钟20秒，我的PL/SQL用时 0.2 秒!
   
5. 
   
6. PL/SQL全面胜出！
   
7. 
   
8. 
   
9. DECLARE
   
10.    TYPE t_num IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
    
11.    TYPE t2_num IS TABLE OF t_num INDEX BY BINARY_INTEGER;
    
12. 
    
13.    TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
    
14. 
    
15.    s t_str;
    
16.    
    
17.    used_c t2_num;     --- in this column whether the number has been used
    
18.    used_r t2_num;     --- in this row whether the number has been used
    
19.    used_a t2_num;     --- in this area whether the number has been used
    
20.    
    
21.    area   t2_num;     ---- mapping from row, column to area
    
22.    
    
23.    v_cnt NUMBER :=0;
    
24.    
    
25.    slot_value t2_num;
    
26.    slot_r t_num;
    
27.    slot_c t_num;
    
28.    
    
29.    v_cnt2 NUMBER :=0;
    
30.    
    
31.    v_idx  NUMBER;
    
32.    
    
33.    slot_value_idx t_num;
    
34.    
    
35.    i  NUMBER;
    
36.    j  NUMBER;
    
37.    k  NUMBER;
    
38. BEGIN
    
39.    --- sample one
    
40.    s(1):= ' 38     2' ;
    
41.    s(2):= '  4 2  5 ' ;
    
42.    s(3):= '     619 ' ;
    
43.    s(4):= '   9  2  ' ;
    
44.    s(5):= '    8    ' ;
    
45.    s(6):= '4 2  1   ' ;
    
46.    s(7):= ' 8       ' ;
    
47.    s(8):= ' 9  3 8  ' ;
    
48.    s(9):= '1     92 ' ;
    
49. 
    
50.    ---- junsansi's sample
    
51.    s(1):= '7  25  98' ;
    
52.    s(2):= '  6    1 ' ;
    
53.    s(3):= '   61 3  ' ;
    
54.    s(4):= '9    1   ' ;
    
55.    s(5):= '    8 4 9' ;
    
56.    s(6):= '  75 28 1' ;
    
57.    s(7):= ' 94  3   ' ;
    
58.    s(8):= '    4923 ' ;
    
59.    s(9):= '61     4 ' ;
    
60. 
    
61.    --- AlEscargot, the most complex SUDOKU puzzle ever
    
62.    s(1):= '1    7 9 ' ;
    
63.    s(2):= ' 3  2   8' ;
    
64.    s(3):= '  96  5  ' ;
    
65.    s(4):= '  53  9  ' ;
    
66.    s(5):= ' 1  8   2' ;
    
67.    s(6):= '6    4   ' ;
    
68.    s(7):= '3      1 ' ;
    
69.    s(8):= ' 4      7' ;
    
70.    s(9):= '  7   3  ' ;
    
71. 
    
72. 
    
73.    FOR i IN 1..9 LOOP
    
74.        FOR j IN 1..9 LOOP
    
75.            used_c(i)(j) := 0;
    
76.            used_r(i)(j) := 0;
    
77.            used_a(i)(j) := 0;
    
78.            
    
79.            area(i)(j) := (CEIL(i/3)-1)*3 + CEIL(j/3);
    
80.        END LOOP;
    
81.    END LOOP;
    
82. 
    
83.    FOR i IN 1..9 LOOP
    
84.        FOR j IN 1..9 LOOP
    
85.            k := TO_NUMBER(TRIM(SUBSTR(s(i),j,1)));
    
86.            IF k>0 THEN
    
87.               used_c(j)(k) :=1;
    
88.               used_r(i)(k) :=1;
    
89.               used_a(area(i)(j))(k) :=1;
    
90.            END IF;
    
91.        END LOOP;
    
92.    END LOOP;
    
93.    
    
94.    FOR i IN 1..9 LOOP
    
95.        FOR j IN 1..9 LOOP
    
96.            IF SUBSTR(s(i),j,1)=' ' THEN
    
97.               v_cnt := v_cnt+1;
    
98.               
    
99.               v_cnt2 :=0;
    
100.               
     
101.               FOR k IN 1..9 LOOP
     
102.                   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
     
103.                      v_cnt2 := v_cnt2 +1;
     
104.                      slot_value(v_cnt)(v_cnt2) := k;
     
105.                   END IF;
     
106.               END LOOP;
     
107.               
     
108.               IF v_cnt2 = 0 THEN
     
109.                  RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||i||','||j);
     
110.               END IF;
     
111.               
     
112.               IF v_cnt2 = 1 THEN        ---- there's only one value for this slot, it's the answer
     
113.                  k := slot_value(v_cnt)(1);
     
114.                  used_c(j)(k) :=1;
     
115.                  used_r(i)(k) :=1;
     
116.                  used_a(area(i)(j))(k) :=1;
     
117.                  v_cnt := v_cnt - 1;
     
118.                  
     
119.                  s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
     
120. 
     
121.               ELSE
     
122.                  slot_r(v_cnt) := i;       ---- position of this slot
     
123.                  slot_c(v_cnt) := j;
     
124.               END IF;
     
125.               
     
126.            END IF;
     
127.        END LOOP;
     
128.    END LOOP;
     
129.    
     
130.    ---- initialize the value indexes of slots
     
131.    v_idx := slot_value.FIRST;
     
132.    
     
133.    WHILE v_idx IS NOT NULL LOOP
     
134.          slot_value_idx(v_idx) := slot_value(v_idx).FIRST;
     
135.          
     
136.          v_idx := slot_value.NEXT(v_idx);
     
137.    END LOOP;
     
138.    
     
139.    v_idx := slot_value.FIRST;
     
140.    
     
141.    WHILE v_idx IS NOT NULL LOOP
     
142.          WHILE slot_value_idx(v_idx) IS NOT NULL LOOP      ---- try all values for this slot
     
143.                i := slot_r(v_idx);
     
144.                j := slot_c(v_idx);
     
145.                k := slot_value(v_idx)(slot_value_idx(v_idx));
     
146.                
     
147.                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
     
148.                   used_c(j)(k) := 1;
     
149.                   used_r(i)(k) := 1;
     
150.                   used_a(area(i)(j))(k) :=1;
     
151.                   EXIT;
     
152.                END IF;
     
153.                
     
154.                slot_value_idx(v_idx) := slot_value(v_idx).NEXT(slot_value_idx(v_idx));
     
155.          END LOOP;
     
156.          
     
157.          IF slot_value_idx(v_idx) IS NULL THEN   ---- all values tried but none is the answer
     
158.             slot_value_idx(v_idx) := slot_value(v_idx).FIRST;   --- reset the index of this slot
     
159.             
     
160.             v_idx := slot_value.PRIOR(v_idx);     --- go back and release the last slot
     
161.             IF v_idx IS NULL THEN      ----- no anwer found
     
162.                DBMS_OUTPUT.PUT_LINE('No Answer Found!');
     
163.                EXIT;
     
164.             END IF;
     
165.             
     
166.             i := slot_r(v_idx);
     
167.             j := slot_c(v_idx);
     
168.             k := slot_value(v_idx)(slot_value_idx(v_idx));
     
169.             
     
170.             used_c(j)(k) := 0;
     
171.             used_r(i)(k) := 0;
     
172.             used_a(area(i)(j))(k) :=0;
     
173.             
     
174.             slot_value_idx(v_idx) := slot_value(v_idx).NEXT(slot_value_idx(v_idx));
     
175.             
     
176.          ELSE
     
177.             v_idx := slot_value.NEXT(v_idx);
     
178.             
     
179.             IF v_idx IS NULL THEN      ----- all slots tried and found an answer
     
180. 
     
181.                v_idx := slot_value.FIRST;
     
182.                
     
183.                WHILE v_idx IS NOT NULL LOOP
     
184.                      i := slot_r(v_idx);
     
185.                      j := slot_c(v_idx);
     
186.                      k := slot_value(v_idx)(slot_value_idx(v_idx));
     
187.                      s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
     
188.    
     
189.                      v_idx := slot_value.NEXT(v_idx);
     
190.                END LOOP;
     
191.                
     
192.                DBMS_OUTPUT.PUT_LINE('Answer Found:');
     
193.                FOR i IN 1..9 LOOP
     
194.                    DBMS_OUTPUT.PUT_LINE(s(i));
     
195.                END LOOP;
     
196.                
     
197.                EXIT;
     
198. 
     
199.             END IF;
     
200.             
     
201.          END IF;
     
202.    END LOOP;
     
203.    
     
204. END;
     
205. /
     
206. 
     
207. 
     
208. 
     
209. 
     

复制代码

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

dingjun123

newkid，哥哥你也太强了吧，小弟佩服之至！

junsansi

原帖由 newkid 于 2008-10-18 03:18 发表




第一位SQL牛人（其实他的MODEL已经和传统SQL天差地别了）的测试用例，他花了40秒，我的PL/SQL用时 1.5 秒。
第二位用SQLSERVER存储过程的，他用了一个号称史上最难的例子，花了5分钟20秒，我的PL/SQL用时 0.2 秒!

PL/SQL全面胜出！


DECLARE
   TYPE t_num IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
   TYPE t2_num IS TABLE OF t_num INDEX BY BINARY_INTEGER;

   TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;

   s t_str;
   
   used_c t2_num;     --- in this column whether the number has been used
   used_r t2_num;     --- in this row whether the number has been used
   used_a t2_num;     --- in this area whether the number has been used
   
   area   t2_num;     ---- mapping from row, column to area
   
   v_cnt NUMBER :=0;
   
   slot_value t2_num;
   slot_r t_num;
   slot_c t_num;
   
   v_cnt2 NUMBER :=0;
   
   v_idx  NUMBER;
   
   slot_value_idx t_num;
   
   i  NUMBER;
   j  NUMBER;
   k  NUMBER;
BEGIN
   --- sample one
   s(1):= ' 38     2' ;
   s(2):= '  4 2  5 ' ;
   s(3):= '     619 ' ;
   s(4):= '   9  2  ' ;
   s(5):= '    8    ' ;
   s(6):= '4 2  1   ' ;
   s(7):= ' 8       ' ;
   s(8):= ' 9  3 8  ' ;
   s(9):= '1     92 ' ;

   ---- junsansi's sample
   s(1):= '7  25  98' ;
   s(2):= '  6    1 ' ;
   s(3):= '   61 3  ' ;
   s(4):= '9    1   ' ;
   s(5):= '    8 4 9' ;
   s(6):= '  75 28 1' ;
   s(7):= ' 94  3   ' ;
   s(8):= '    4923 ' ;
   s(9):= '61     4 ' ;

   --- AlEscargot, the most complex SUDOKU puzzle ever
   s(1):= '1    7 9 ' ;
   s(2):= ' 3  2   8' ;
   s(3):= '  96  5  ' ;
   s(4):= '  53  9  ' ;
   s(5):= ' 1  8   2' ;
   s(6):= '6    4   ' ;
   s(7):= '3      1 ' ;
   s(8):= ' 4      7' ;
   s(9):= '  7   3  ' ;


   FOR i IN 1..9 LOOP
       FOR j IN 1..9 LOOP
           used_c(i)(j) := 0;
           used_r(i)(j) := 0;
           used_a(i)(j) := 0;
           
           area(i)(j) := (CEIL(i/3)-1)*3 + CEIL(j/3);
       END LOOP;
   END LOOP;

   FOR i IN 1..9 LOOP
       FOR j IN 1..9 LOOP
           k := TO_NUMBER(TRIM(SUBSTR(s(i),j,1)));
           IF k>0 THEN
              used_c(j)(k) :=1;
              used_r(i)(k) :=1;
              used_a(area(i)(j))(k) :=1;
           END IF;
       END LOOP;
   END LOOP;
   
   FOR i IN 1..9 LOOP
       FOR j IN 1..9 LOOP
           IF SUBSTR(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;
                  END IF;
              END LOOP;
              
              IF v_cnt2 = 0 THEN
                 RAISE_APPLICATION_ERROR(-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) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);

              ELSE
                 slot_r(v_cnt) := i;       ---- position of this slot
                 slot_c(v_cnt) := j;
              END IF;
              
           END IF;
       END LOOP;
   END LOOP;
   
   ---- initialize the value indexes of slots
   v_idx := slot_value.FIRST;
   
   WHILE v_idx IS NOT NULL LOOP
         slot_value_idx(v_idx) := slot_value(v_idx).FIRST;
         
         v_idx := slot_value.NEXT(v_idx);
   END LOOP;
   
   v_idx := slot_value.FIRST;
   
   WHILE v_idx IS NOT NULL LOOP
         WHILE slot_value_idx(v_idx) IS NOT NULL LOOP      ---- try all values for this slot
               i := slot_r(v_idx);
               j := slot_c(v_idx);
               k := slot_value(v_idx)(slot_value_idx(v_idx));
               
               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
                  used_c(j)(k) := 1;
                  used_r(i)(k) := 1;
                  used_a(area(i)(j))(k) :=1;
                  EXIT;
               END IF;
               
               slot_value_idx(v_idx) := slot_value(v_idx).NEXT(slot_value_idx(v_idx));
         END LOOP;
         
         IF slot_value_idx(v_idx) IS NULL THEN   ---- all values tried but none is the answer
            slot_value_idx(v_idx) := slot_value(v_idx).FIRST;   --- reset the index of this slot
            
            v_idx := slot_value.PRIOR(v_idx);     --- go back and release the last slot
            IF v_idx IS NULL THEN      ----- no anwer found
               DBMS_OUTPUT.PUT_LINE('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;
            
            slot_value_idx(v_idx) := slot_value(v_idx).NEXT(slot_value_idx(v_idx));
            
         ELSE
            v_idx := slot_value.NEXT(v_idx);
            
            IF v_idx IS NULL THEN      ----- all slots tried and found an answer

               v_idx := slot_value.FIRST;
               
               WHILE v_idx IS NOT NULL LOOP
                     i := slot_r(v_idx);
                     j := slot_c(v_idx);
                     k := slot_value(v_idx)(slot_value_idx(v_idx));
                     s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
   
                     v_idx := slot_value.NEXT(v_idx);
               END LOOP;
               
               DBMS_OUTPUT.PUT_LINE('Answer Found:');
               FOR i IN 1..9 LOOP
                   DBMS_OUTPUT.PUT_LINE(s(i));
               END LOOP;
               
               EXIT;

            END IF;
            
         END IF;
   END LOOP;
   
END;
/

jiqing1004

newkid  真是强悍啊  

newkid

这个解法其实很简单，类似“八皇后问题”，大家上数据结构课都做过这个练习吧？我一开始都不相信效果有这么好。
等会我有空再稍微优化一下。

newkid

1. 
   
2. 
   
3. 下面的另一写法是我试图进行优化的结果，我本来打算借鉴ORACLE连接表时用小表驱动大表的思路，在进入循环之前做个排序。试验证明对很多题型是有效的，我测的都在0.X或0.0X秒，但对那个AlEscargot题反而从0.15秒上升到5.x 秒。看来运气还是很重要，有时候答案很快就碰上了。
   
4. 
   
5. 这个新写法利用SQL对内存数组（嵌套表）进行排序，总算和ORACLE有了点关系，算是一种技巧吧：
   
6. SELECT CAST(MULTISET(SELECT * FROM TABLE(CAST(empty_slots AS table_slot)) ORDER BY cnt,r,c) AS table_slot)
   
7.   INTO empty_slots
   
8.   FROM DUAL;
   
9. 
   
10. 我又对Anton Scheffer老兄的SQL作了些测试，有时候他的SQL也是很快的，但他自己的第一个例子却要花40来秒，还是运气问题。
    
11. 
    
12. 
    
13. CREATE OR REPLACE TYPE t_num IS TABLE OF NUMBER
    
14. /
    
15. 
    
16. CREATE OR REPLACE TYPE type_slot AS OBJECT  (
    
17.             r           NUMBER
    
18.            ,c           NUMBER
    
19.            ,cnt         NUMBER
    
20.            ,idx         NUMBER
    
21.   )
    
22. /
    
23. 
    
24. CREATE OR REPLACE TYPE table_slot AS TABLE OF type_slot
    
25. /
    
26. 
    
27. 
    
28. DECLARE
    
29.    TYPE t2_num IS TABLE OF t_num INDEX BY BINARY_INTEGER;
    
30.    TYPE t3_num IS TABLE OF t2_num INDEX BY BINARY_INTEGER;
    
31.    TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
    
32. 
    
33.    s t_str;
    
34.    
    
35.    used_c t2_num;     --- in this column whether the number has been used
    
36.    used_r t2_num;     --- in this row whether the number has been used
    
37.    used_a t2_num;     --- in this area whether the number has been used
    
38.    
    
39.    area   t2_num;     ---- mapping from row, column to area
    
40.    
    
41.    slot_values t3_num;
    
42.    
    
43.    v_idx  NUMBER;
    
44.    
    
45.    i  NUMBER;
    
46.    j  NUMBER;
    
47.    k  NUMBER;
    
48.    
    
49.    empty_set  t_num := t_num(0,0,0,0,0,0,0,0,0);
    
50.    
    
51.    empty_slots table_slot := table_slot();
    
52.    
    
53.    v_continue NUMBER;
    
54.    v_del      NUMBER;
    
55. 
    
56. BEGIN
    
57. 
    
58.    ---- junsansi's sample
    
59.    s(1):= '7  25  98' ;
    
60.    s(2):= '  6    1 ' ;
    
61.    s(3):= '   61 3  ' ;
    
62.    s(4):= '9    1   ' ;
    
63.    s(5):= '    8 4 9' ;
    
64.    s(6):= '  75 28 1' ;
    
65.    s(7):= ' 94  3   ' ;
    
66.    s(8):= '    4923 ' ;
    
67.    s(9):= '61     4 ' ;
    
68. 
    
69.    --- AlEscargot, the most complex SUDOKU puzzle ever
    
70.    s(1):= '1    7 9 ' ;
    
71.    s(2):= ' 3  2   8' ;
    
72.    s(3):= '  96  5  ' ;
    
73.    s(4):= '  53  9  ' ;
    
74.    s(5):= ' 1  8   2' ;
    
75.    s(6):= '6    4   ' ;
    
76.    s(7):= '3      1 ' ;
    
77.    s(8):= ' 4      7' ;
    
78.    s(9):= '  7   3  ' ;
    
79. 
    
80.    --- sample one
    
81.    s(1):= '3 58  176';
    
82.    s(2):= '1   5   2';
    
83.    s(3):= '      549';
    
84.    s(4):= ' 52 986  ';
    
85.    s(5):= '43  12  7';
    
86.    s(6):= '   5  4  ';
    
87.    s(7):= '5   6 894';
    
88.    s(8):= ' 69 7   5';
    
89.    s(9):= '   9   61';
    
90. 
    
91. 
    
92.    FOR i IN 1..9 LOOP
    
93.        used_r(i) := empty_set;
    
94.        used_c(i) := empty_set;
    
95.        used_a(i) := empty_set;
    
96.        area(i)   := empty_set;
    
97.       
    
98.        FOR j IN 1..9 LOOP
    
99.            area(i)(j) := (CEIL(i/3)-1)*3 + CEIL(j/3);
    
100.            slot_values(i)(j) := empty_set;
     
101.        END LOOP;
     
102.    END LOOP;
     
103. 
     
104.    FOR i IN 1..9 LOOP
     
105.        FOR j IN 1..9 LOOP
     
106.            k := TO_NUMBER(TRIM(SUBSTR(s(i),j,1)));
     
107.            IF k>0 THEN
     
108.               used_r(i)(k) :=1;
     
109.               used_c(j)(k) :=1;
     
110.               used_a(area(i)(j))(k) :=1;
     
111.               
     
112.               FOR v_del IN 1..9 LOOP
     
113.                   slot_values(i)(v_del).DELETE(k);
     
114.                   slot_values(v_del)(j).DELETE(k);
     
115.                   slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
     
116.               END LOOP;
     
117. 
     
118.            ELSE
     
119. 
     
120.               empty_slots.EXTEND;
     
121.               empty_slots(empty_slots.COUNT) := type_slot(i,j,0,0);
     
122.            END IF;
     
123.        END LOOP;
     
124.    END LOOP;
     
125. 
     
126.    v_continue :=1;
     
127.    WHILE v_continue = 1 AND empty_slots.COUNT>0 LOOP
     
128.          v_continue := 0;
     
129.          v_idx := empty_slots.FIRST;
     
130.          WHILE v_idx IS NOT NULL LOOP
     
131.                empty_slots(v_idx).cnt := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).COUNT;
     
132.                IF empty_slots(v_idx).cnt = 0 THEN
     
133.                   RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||empty_slots(v_idx).r||','||empty_slots(v_idx).c);
     
134.                ELSIF empty_slots(v_idx).cnt = 1 THEN
     
135.                   i := empty_slots(v_idx).r;
     
136.                   j := empty_slots(v_idx).c;
     
137.                   k := slot_values(i)(j).FIRST;
     
138.                   used_r(i)(k) :=1;
     
139.                   used_c(j)(k) :=1;
     
140.                   used_a(area(i)(j))(k) :=1;
     
141.                   
     
142.                   FOR v_del IN 1..9 LOOP
     
143.                       slot_values(i)(v_del).DELETE(k);
     
144.                       slot_values(v_del)(j).DELETE(k);
     
145.                       slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
     
146.                   END LOOP;
     
147.                   
     
148.                   v_continue := 1;
     
149.                   v_del := v_idx;
     
150.                   s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
     
151.                ELSE
     
152.                   v_del := 0;
     
153.                END IF;
     
154.                
     
155.                v_idx := empty_slots.NEXT(v_idx);
     
156.                
     
157.                IF v_del>0 THEN
     
158.                   empty_slots.DELETE(v_del);
     
159.                END IF;
     
160.                
     
161.          END LOOP;
     
162.    END LOOP;
     
163. 
     
164.    v_continue := 1;
     
165. 
     
166.    IF empty_slots.COUNT>0 THEN
     
167.       ----- 借鉴小表驱动大表的思路进行排序预处理。实际应用效果不佳，此SELECT可以去掉。
     
168.       --SELECT CAST(MULTISET(SELECT * FROM TABLE(CAST(empty_slots AS table_slot)) ORDER BY cnt,r,c) AS table_slot)
     
169.       --  INTO empty_slots
     
170.       --  FROM DUAL;
     
171.    
     
172.       v_idx := empty_slots.FIRST;
     
173.       empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST;
     
174.       
     
175.       WHILE v_idx IS NOT NULL LOOP
     
176.             WHILE empty_slots(v_idx).idx IS NOT NULL LOOP      ---- try all values for this slot
     
177.                   i := empty_slots(v_idx).r;
     
178.                   j := empty_slots(v_idx).c;
     
179.                   k := empty_slots(v_idx).idx;   
     
180.    
     
181.                   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
     
182.                      used_c(j)(k) := 1;
     
183.                      used_r(i)(k) := 1;
     
184.                      used_a(area(i)(j))(k) :=1;
     
185.                      EXIT;
     
186.                   END IF;
     
187.                   
     
188.                   empty_slots(v_idx).idx := slot_values(i)(j).NEXT(empty_slots(v_idx).idx);
     
189.             END LOOP;
     
190.             
     
191.             IF empty_slots(v_idx).idx IS NULL THEN   ---- all values tried but none is the answer
     
192.                -- slot_value_idx(v_idx) := slot_value(v_idx).FIRST;   --- reset the index of this slot
     
193.                
     
194.                v_idx := empty_slots.PRIOR(v_idx);     --- go back and release the last slot
     
195.                IF v_idx IS NULL THEN      ----- no anwer found
     
196.                   v_continue := 0;
     
197.                   EXIT;
     
198.                END IF;
     
199.    
     
200.                i := empty_slots(v_idx).r;
     
201.                j := empty_slots(v_idx).c;
     
202.                k := empty_slots(v_idx).idx;      
     
203.                
     
204.                used_c(j)(k) := 0;
     
205.                used_r(i)(k) := 0;
     
206.                used_a(area(i)(j))(k) :=0;
     
207.                
     
208.                empty_slots(v_idx).idx := slot_values(i)(j).NEXT(empty_slots(v_idx).idx);
     
209.                
     
210.             ELSE
     
211.                v_idx := empty_slots.NEXT(v_idx);
     
212.                
     
213.                IF v_idx IS NULL THEN      ----- all slots tried and found an answer
     
214.                   EXIT;
     
215.                END IF;
     
216.                empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST;
     
217.             END IF;
     
218.       END LOOP;
     
219.    
     
220.    END IF;
     
221. 
     
222.    IF v_continue = 1 THEN
     
223.       v_idx := empty_slots.FIRST;
     
224.       
     
225.       WHILE v_idx IS NOT NULL LOOP
     
226.             i := empty_slots(v_idx).r;
     
227.             j := empty_slots(v_idx).c;
     
228.             k := empty_slots(v_idx).idx;      
     
229.             s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
     
230.    
     
231.             v_idx := empty_slots.NEXT(v_idx);
     
232.       END LOOP;
     
233.       
     
234.       DBMS_OUTPUT.PUT_LINE('Answer Found:');
     
235.       FOR i IN 1..9 LOOP
     
236.           DBMS_OUTPUT.PUT_LINE(s(i));
     
237.       END LOOP;
     
238.    ELSE
     
239.       DBMS_OUTPUT.PUT_LINE('No Answer Found!');
     
240.    
     
241.    END IF;
     
242. 
     
243. END;
     
244. /
     
245. 
     
246. 后记：去这里下载了160高级题，经过比较排序和不排序预处理的解题速度，竟然是不排序的更快，唉白作优化了。
     
247. [url]http://www.sudokufans.org.cn/shudo/download/160hard.rar[/url]
     
248. 
     

复制代码

[ 本帖最后由 newkid 于 2008-10-21 06:40 编辑 ]

cuicg

newkid 大师难道不睡觉么？小弟对你的渊博知识佩服的五体投地，对你的专注精神更加敬仰！

zhangweicai74

原帖由 cuicg 于 2008-10-21 08:30 发表
newkid 大师难道不睡觉么？小弟对你的渊博知识佩服的五体投地，对你的专注精神更加敬仰！

时差.
人家正是上班时间,能睡觉么?