PLSQL解sudoku的方法
?
??? 2008年最后一篇，自然要來一點重量級內容，這篇摘錄了論壇里newkid大牛寫的解sudoku的PLSQL程序，特別值得推薦的就是分三種思想分別求解，以及PLSQL里數組的應用，基本上在平常的工作中很難用到，所以很有學習的價值。原文的地址如下：
???
?
1、sudoku_tests.sql
?
??? <摘錄了160個sudoku的題目，以及測試代碼，對程序進行檢測>
CREATE TABLE sudoku_tests (
?????? id????????? NUMBER
????? ,cells?????? VARCHAR2(81)
????? ,used_time1? NUMBER(10,3)
????? ,used_time2? NUMBER(10,3)
????? ,used_time3? NUMBER(10,3)
????? );
?
?
INSERT INTO sudoku_tests(id,cells) VALUES(1? ,'016400000200009000400000062070230100100000003003087040960000005000800007000006820');
INSERT INTO sudoku_tests(id,cells) VALUES(2? ,'049008605003007000000000030000400800060815020001009000010000000000600400804500390');
INSERT INTO sudoku_tests(id,cells) VALUES(3? ,'760500000000060008000000403200400800080000030005001007809000000600010000000003041');
INSERT INTO sudoku_tests(id,cells) VALUES(4? ,'000605000003020800045090270500000001062000540400000007098060450006040700000203000');
INSERT INTO sudoku_tests(id,cells) VALUES(5? ,'409000705000010000006207800200000009003704200800000004002801500000060000905000406');
INSERT INTO sudoku_tests(id,cells) VALUES(6? ,'000010030040070501002008006680000003000302000300000045200500800801040020090020000');
INSERT INTO sudoku_tests(id,cells) VALUES(7? ,'080070030260050018000000400000602000390010086000709000004000800810040052050090070');
INSERT INTO sudoku_tests(id,cells) VALUES(8? ,'000093006000800900020006100000080053006000200370050000002500040001009000700130000');
INSERT INTO sudoku_tests(id,cells) VALUES(9? ,'096500780007001000000000100604009070010802060080400203008000000000900300041008920');
INSERT INTO sudoku_tests(id,cells) VALUES(10 ,'000000000140070000005106900021005080400000007080700620009304500000020018000000000');
INSERT INTO sudoku_tests(id,cells) VALUES(11 ,'000600000047100000890040013001004020200090008030800500450070036000006840000005000');
INSERT INTO sudoku_tests(id,cells) VALUES(12 ,'003070900000901000200308007072000510400000002015000840900104005000503000006020300');
INSERT INTO sudoku_tests(id,cells) VALUES(13 ,'907002800300004057100070000009003000000020000000600200000010008570300004002700905');
INSERT INTO sudoku_tests(id,cells) VALUES(14 ,'600000450080002000009070100000003940000040000012800000001080700000200030097000006');
INSERT INTO sudoku_tests(id,cells) VALUES(15 ,'600000008000000100001307000004900280003102900092005300000203400005000000100000006');
INSERT INTO sudoku_tests(id,cells) VALUES(16 ,'100000008050000070702000406900801007060000090010020050003080600080000040070503080');
INSERT INTO sudoku_tests(id,cells) VALUES(17 ,'004705900000801000600040005430000082008000400920000063200030001000502000007608200');
INSERT INTO sudoku_tests(id,cells) VALUES(18 ,'080306040100020008000050000300000006067080950800000002000070000600010003070904080');
INSERT INTO sudoku_tests(id,cells) VALUES(19 ,'000000600004500097002800010070003001000050000200900080020006300130004700009000000');
INSERT INTO sudoku_tests(id,cells) VALUES(20 ,'000000009000020003046900050310200090000105000080009017030008420900030000100000000');
INSERT INTO sudoku_tests(id,cells) VALUES(21 ,'006300200708000000100050080400005030070010020090400008050040009000000506004006300');
INSERT INTO sudoku_tests(id,cells) VALUES(22 ,'290700000004020010003004000050070060900203007020090030000500400010080600000006071');
INSERT INTO sudoku_tests(id,cells) VALUES(23 ,'000000000500010004030605210090020081007000400260030050026803070900050008000000000');
INSERT INTO sudoku_tests(id,cells) VALUES(24 ,'000000060005007009079080310130600000000000000000004078083050790900400600020000000');
INSERT INTO sudoku_tests(id,cells) VALUES(25 ,'000509000007000305000008170001900006020030010600004500084200000509000400000703000');
INSERT INTO sudoku_tests(id,cells) VALUES(26 ,'309000000000030050041600000400700003080020040100004009000008120030050000000000906');
INSERT INTO sudoku_tests(id,cells) VALUES(27 ,'000604002000039050008000400900003041003000500670100009002000100080490000700306000');
INSERT INTO sudoku_tests(id,cells) VALUES(28 ,'000000007040800095005031000400003020006010800030200009000420700190006040600000000');
INSERT INTO sudoku_tests(id,cells) VALUES(29 ,'500904008001000070000007090007000400906805702003000600080100000060000900700406005');
INSERT INTO sudoku_tests(id,cells) VALUES(30 ,'003600507000930000080007000058000000106000908000000340000400090000058000507009200');
INSERT INTO sudoku_tests(id,cells) VALUES(31 ,'005000600004306900800209005040010080000000000002605700000000000006507300010000040');
INSERT INTO sudoku_tests(id,cells) VALUES(32 ,'060000010790010032008000400000849000040607050000153000009000700670030091050000060');
INSERT INTO sudoku_tests(id,cells) VALUES(33 ,'008009061010500009700030400090300008005000200800005030004020006300004070920800100');
INSERT INTO sudoku_tests(id,cells) VALUES(34 ,'800000209000100007005002000060050004004080700300090020000900600200005000607000003');
INSERT INTO sudoku_tests(id,cells) VALUES(35 ,'090008370000000000300605012000010006031060820200040000940201008000000000017400060');
INSERT INTO sudoku_tests(id,cells) VALUES(36 ,'100260009070000050000008200003070004900846003800030600004600300080000040700081002');
INSERT INTO sudoku_tests(id,cells) VALUES(37 ,'007006000004000006060109080006270000080000030000038900010802090500000800000300100');
INSERT INTO sudoku_tests(id,cells) VALUES(38 ,'002000900090070030004000700028107650000050000007304100060000080001438200000000000');
INSERT INTO sudoku_tests(id,cells) VALUES(39 ,'060000800000040500500200047008009060070105090030800100840006003002070000003000010');
INSERT INTO sudoku_tests(id,cells) VALUES(40 ,'008000100070040030600507004007080600040602050006050300700205003020070080009000200');
INSERT INTO sudoku_tests(id,cells) VALUES(41 ,'000009360010020000004000002003102006050070040100406900900000500000060030028700000');
INSERT INTO sudoku_tests(id,cells) VALUES(42 ,'003004000602300000050600807508000009000070000700000201407008020000005904000700600');
INSERT INTO sudoku_tests(id,cells) VALUES(43 ,'050901060700050003006000900800020004070403020400060005001000700600010008030504010');
INSERT INTO sudoku_tests(id,cells) VALUES(44 ,'000300007806012000004005200000030050508000406040070000003800600000940301100003000');
INSERT INTO sudoku_tests(id,cells) VALUES(45 ,'200070004006000800090308050003109600800000005001507300040803090002000400600040007');
INSERT INTO sudoku_tests(id,cells) VALUES(46 ,'005000700020503080800090005030050070008704100070030040100040009040902010009000600');
INSERT INTO sudoku_tests(id,cells) VALUES(47 ,'600801003080402010000090000890000052004000900510000037000010000030904020700603008');
INSERT INTO sudoku_tests(id,cells) VALUES(48 ,'500003007001070000000805160208000500010090040005000709026709300000010900800200001');
INSERT INTO sudoku_tests(id,cells) VALUES(49 ,'006908200030050080800000004400501003050000040200804007300000005060080010005107600');
INSERT INTO sudoku_tests(id,cells) VALUES(50 ,'080063001400500030000004800060000902500000006207000080004600000090005003300720010');
INSERT INTO sudoku_tests(id,cells) VALUES(51 ,'000002900050900800008001037060130208000804000803056090610400300004008070007600000');
INSERT INTO sudoku_tests(id,cells) VALUES(52 ,'003000200014000390080000040030807050009040700007206800300000004000529000090070010');
INSERT INTO sudoku_tests(id,cells) VALUES(53 ,'300104008008090100040000070200708004060000010700903005020000090001080400400309001');
INSERT INTO sudoku_tests(id,cells) VALUES(54 ,'100703009002010600000406000380000064650000023720000058000508000008070200900602001');
INSERT INTO sudoku_tests(id,cells) VALUES(55 ,'008102050020050800003000000070380500000209000009015060000000200005090010040508700');
INSERT INTO sudoku_tests(id,cells) VALUES(56 ,'200010009000904000007805600045000920300000008079000140008109300000503000900040006');
INSERT INTO sudoku_tests(id,cells) VALUES(57 ,'300000004020805090007090600060050010008704300070080020001020500080109040700000001');
INSERT INTO sudoku_tests(id,cells) VALUES(58 ,'570904023800000004003000100300060005000401000100070002002000900700000001680502047');
INSERT INTO sudoku_tests(id,cells) VALUES(59 ,'802000000300600500000050070080590040009000600060071090070020000001008007000000803');
INSERT INTO sudoku_tests(id,cells) VALUES(60 ,'006020079000000001005630000003470000020009705000005400900008104600090000087000000');
INSERT INTO sudoku_tests(id,cells) VALUES(61 ,'070000060040507090009108300000802000010000020002903500200030004400206009005000600');
INSERT INTO sudoku_tests(id,cells) VALUES(62 ,'010050080500603007006000500070060090600204001020030040002000400700106003080020060');
INSERT INTO sudoku_tests(id,cells) VALUES(63 ,'060040050100000008008703600002107900800000002009502100001304200900000003030070090');
INSERT INTO sudoku_tests(id,cells) VALUES(64 ,'080003900060400015300010600700000050002070800040000009001020503450006090006100070');
INSERT INTO sudoku_tests(id,cells) VALUES(65 ,'010502080408000501090000030600050003000907000500010009050000040104000208030408070');
INSERT INTO sudoku_tests(id,cells) VALUES(66 ,'130607092700201003000030000320000061005000300910000057000010000500403008270508036');
INSERT INTO sudoku_tests(id,cells) VALUES(67 ,'800204007009030800070000090700106002060000070900402006090000050004060700300809004');
INSERT INTO sudoku_tests(id,cells) VALUES(68 ,'800203005040050010003000800200506001060000030900708006006000100090020040100304007');
INSERT INTO sudoku_tests(id,cells) VALUES(69 ,'090000020003908700500702009370040061006000900140070083900605008005107600010000050');
INSERT INTO sudoku_tests(id,cells) VALUES(70 ,'730080016800609003000000000050407090200000004010502070000000000500104002370020045');
INSERT INTO sudoku_tests(id,cells) VALUES(71 ,'000600000810400900040010030001300500030060020002007600070030090005009068000005000');
INSERT INTO sudoku_tests(id,cells) VALUES(72 ,'032000590000000000007569300008706400004803700020000080080194060060070010000000000');
INSERT INTO sudoku_tests(id,cells) VALUES(73 ,'020901040900702003000050000240000089009000400380000067000080000400207006050103070');
INSERT INTO sudoku_tests(id,cells) VALUES(74 ,'000000000034105720016000450040080010009070200070000060700802006068090540000000000');
INSERT INTO sudoku_tests(id,cells) VALUES(75 ,'059060340000000000100703006608000902700080001030000080000000000400207003007809100');
INSERT INTO sudoku_tests(id,cells) VALUES(76 ,'406905803100030006093000750050000080800000002000894000620000037000000000001709600');
INSERT INTO sudoku_tests(id,cells) VALUES(77 ,'009806300000040000400507009903000602010000080508000901700104006000060000001908200');
INSERT INTO sudoku_tests(id,cells) VALUES(78 ,'700104008009000600030020010800701005002000100300402009020040090007000300100203006');
INSERT INTO sudoku_tests(id,cells) VALUES(79 ,'006700084040005600000090000000030005930000021100050000000070000002400010780009300');
INSERT INTO sudoku_tests(id,cells) VALUES(80 ,'008000090000095600010070300003000009046020710700000400002080030005940000060000200');
INSERT INTO sudoku_tests(id,cells) VALUES(81 ,'091050800500704006000100000020000900100060003006000050000007000600803004009040270');
INSERT INTO sudoku_tests(id,cells) VALUES(82 ,'007000500020000090034105670006408100000050000005703200063209410010000020002000300');
INSERT INTO sudoku_tests(id,cells) VALUES(83 ,'060040030300000008001307500005080700700651002006070300003709100200000003050030090');
INSERT INTO sudoku_tests(id,cells) VALUES(84 ,'120000006000090070000045100900506000006010500000207001007450000080020000400000089');
INSERT INTO sudoku_tests(id,cells) VALUES(85 ,'200040608005060000000009010080700900300000002009004080070300000000050700803020005');
INSERT INTO sudoku_tests(id,cells) VALUES(86 ,'400020003050801070007090500060000010501000307030000090005040100090608050200010006');
INSERT INTO sudoku_tests(id,cells) VALUES(87 ,'200805009004000800060010020400203008005000100700901003090020060003000700600504001');
INSERT INTO sudoku_tests(id,cells) VALUES(88 ,'040900100000008060690000002009003004050020070200100600700000089020800000004002050');
INSERT INTO sudoku_tests(id,cells) VALUES(89 ,'042001000800000009000630000009007100650000082001200400000064000200000003000100560');
INSERT INTO sudoku_tests(id,cells) VALUES(90 ,'080401090900050001001296400705000906069000320802000107007945800400010009090602010');
INSERT INTO sudoku_tests(id,cells) VALUES(91 ,'005003020700050300010004805201000000070030010000000709809200640002060008060800100');
INSERT INTO sudoku_tests(id,cells) VALUES(92 ,'010607050700000001004000800300010007000502000900070004006000100200000009070405060');
INSERT INTO sudoku_tests(id,cells) VALUES(93 ,'600500002019080000070000040040100870000070000057003020020000050000090180800006004');
INSERT INTO sudoku_tests(id,cells) VALUES(94 ,'020008000907030100050200930005300004070060010200009500042003070008050301000800020');
INSERT INTO sudoku_tests(id,cells) VALUES(95 ,'560030900200090501000700000005008006070000080400900700000003000902040003006010054');
INSERT INTO sudoku_tests(id,cells) VALUES(96 ,'003708600000020000200509007107000508020000090904000206600802001000040000008601700');
INSERT INTO sudoku_tests(id,cells) VALUES(97 ,'780000021900501003003000400030904010000000000090807060001000900800209005560000042');
INSERT INTO sudoku_tests(id,cells) VALUES(98 ,'300005006400270000008009000590300000700060009000004017000800600000012008800700004');
INSERT INTO sudoku_tests(id,cells) VALUES(99 ,'600050001090301040007000200030104050100000002080705010001000600070906020500030008');
INSERT INTO sudoku_tests(id,cells) VALUES(100,'830000000000400010100053200060200400007080100008009060006810004090005000000000021');
INSERT INTO sudoku_tests(id,cells) VALUES(101,'000000700090500080007009600010090024020070060580060010004200900060008050005000000');
INSERT INTO sudoku_tests(id,cells) VALUES(102,'000000602000003040000480390014800000500030001000002730087041000090300000601000000');
INSERT INTO sudoku_tests(id,cells) VALUES(103,'300000009206030704070904080000040000000308000060109020050000090608000502012000670');
INSERT INTO sudoku_tests(id,cells) VALUES(104,'100207006000906000004010200810000073005020400430000025001070800000802000500103004');
INSERT INTO sudoku_tests(id,cells) VALUES(105,'500208006003010200010000080600904001020000040400701002080000030001050900900603007');
INSERT INTO sudoku_tests(id,cells) VALUES(106,'005040790000007006800010002000800010901000203020001000400050007200300000069070500');
INSERT INTO sudoku_tests(id,cells) VALUES(107,'012000004700600900905003080050430100000805000008016050090300805001007003500000640');
INSERT INTO sudoku_tests(id,cells) VALUES(108,'600003507000020080003900006009700001010000030200006400100004200090080000302500008');
INSERT INTO sudoku_tests(id,cells) VALUES(109,'070000030081903500006070000000100003800020009400006000000060400004508160020000080');
INSERT INTO sudoku_tests(id,cells) VALUES(110,'060010502020008000400500008094002006000000000800300970600001007000600040509040080');
INSERT INTO sudoku_tests(id,cells) VALUES(111,'020507030900203008000010000860401023007000800530809046000090000400605009090102050');
INSERT INTO sudoku_tests(id,cells) VALUES(112,'000700000690040000042005000100200500020000090004009006008900100460050720070002030');
INSERT INTO sudoku_tests(id,cells) VALUES(113,'040301080200000003005020100700106005004000200600402009009010700500000008030908020');
INSERT INTO sudoku_tests(id,cells) VALUES(114,'061000200050901006000000080005060000040208060000030700020000000900604030008000470');
INSERT INTO sudoku_tests(id,cells) VALUES(115,'004803200000705000300020008480000061007000500690000032200090007000407000008602300');
INSERT INTO sudoku_tests(id,cells) VALUES(116,'310000057450687031000030000700204006003000500200803009000020000620548073580000062');
INSERT INTO sudoku_tests(id,cells) VALUES(117,'000073000000245000072100300360000900005000800004000053009006120000421000000350000');
INSERT INTO sudoku_tests(id,cells) VALUES(118,'001080500000109000400205001037000650500000002049000170900507006000402000005060900');
INSERT INTO sudoku_tests(id,cells) VALUES(119,'300800710001027004080000002800004090030010070070900003200000040500460300047002005');
INSERT INTO sudoku_tests(id,cells) VALUES(120,'008020000017503000450001600030005140800000009041700060004600035000304290000090400');
INSERT INTO sudoku_tests(id,cells) VALUES(121,'036708000150400000807050000360000002008000100400000079000070905000005048000609310');
INSERT INTO sudoku_tests(id,cells) VALUES(122,'200103009009000800070080040100020006007604200600090001060030050004000600900207004');
INSERT INTO sudoku_tests(id,cells) VALUES(123,'500904001090307060001050900200000006900786005060102070100000002029000640000000000');
INSERT INTO sudoku_tests(id,cells) VALUES(124,'830701056690050027000000000200080004010405030400010009000000000520070068380206095');
INSERT INTO sudoku_tests(id,cells) VALUES(125,'000000008020106000001080530700000400040307090005000001053010600000609070900000000');
INSERT INTO sudoku_tests(id,cells) VALUES(126,'000300000000060210016904080001000350020000060038000900050801420087030000000006000');
INSERT INTO sudoku_tests(id,cells) VALUES(127,'090000010200608007007000500010070040000905000050020030001000300600209004040000050');
INSERT INTO sudoku_tests(id,cells) VALUES(128,'800030005000204000007809100091000650500000003032000890004907500000502000900060007');
INSERT INTO sudoku_tests(id,cells) VALUES(129,'300040009009000100050906030005704900400000002003501700040803020006000300500060008');
INSERT INTO sudoku_tests(id,cells) VALUES(130,'600903004009600100030000000200490060004050300070032005000000010007009600300805002');
INSERT INTO sudoku_tests(id,cells) VALUES(131,'807001500030980000400300002058100006060000050900003280500006001000059040002800605');
INSERT INTO sudoku_tests(id,cells) VALUES(132,'090080020000947000000203000027406980100000005006105700005000800410000039800000004');
INSERT INTO sudoku_tests(id,cells) VALUES(133,'000005000009610040300070002000400310004000500085007000800020009070098400000100000');
INSERT INTO sudoku_tests(id,cells) VALUES(134,'000000000007020800863000152600809004030000010004000200090308020040507090006000400');
INSERT INTO sudoku_tests(id,cells) VALUES(135,'006040002040001000800006000000105970002000500073804000000300004000500010900070200');
INSERT INTO sudoku_tests(id,cells) VALUES(136,'001090700300507004050462030000308000043000510000601000010935020200106005008070300');
INSERT INTO sudoku_tests(id,cells) VALUES(137,'005006300000410900700000065030092001060103080800640030270000003009038000003900400');
INSERT INTO sudoku_tests(id,cells) VALUES(138,'000720100100805003000000040400010006070000020500090004050000000600104007004063000');
INSERT INTO sudoku_tests(id,cells) VALUES(139,'000105000400000001302000508040000070600010004900000002000050000050708060007634800');
INSERT INTO sudoku_tests(id,cells) VALUES(140,'005200800070030090900400002000000609050010040809000000200003004010040060008001900');
INSERT INTO sudoku_tests(id,cells) VALUES(141,'005080000070309000900000304480600000000050000000007031604000002000802070000030500');
INSERT INTO sudoku_tests(id,cells) VALUES(142,'008000100100267003020080070060509010009000300030402060080040050500826001003000800');
INSERT INTO sudoku_tests(id,cells) VALUES(143,'230000060600009708000605010003700690000000000097004800020106000804200006010000029');
INSERT INTO sudoku_tests(id,cells) VALUES(144,'920035100050000000008690000804500020000000000010004908000029700000000060005460092');
INSERT INTO sudoku_tests(id,cells) VALUES(145,'003000000090040020005701006004010600010408090008020700800209000050080010000000400');
INSERT INTO sudoku_tests(id,cells) VALUES(146,'005302004000000500020600008100005000030981060000200009400006010008000000300508400');
INSERT INTO sudoku_tests(id,cells) VALUES(147,'600807001010326070000104000146000859030000010759000243000409000060513020300208005');
INSERT INTO sudoku_tests(id,cells) VALUES(148,'001050200050107080200309005013000920900000004024000650100804002070205010002060500');
INSERT INTO sudoku_tests(id,cells) VALUES(149,'070080000100420900008301070017000500850000031009000280090604800003018005000030060');
INSERT INTO sudoku_tests(id,cells) VALUES(150,'270040081500800007000000300000308090700050002060204000006000900300005004940030015');
INSERT INTO sudoku_tests(id,cells) VALUES(151,'040310002203006000060809000802000540600000007059000206000608020000100605100092030');
INSERT INTO sudoku_tests(id,cells) VALUES(152,'000000370009750001080103000040300100000080000007006050000208090800014700092000000');
INSERT INTO sudoku_tests(id,cells) VALUES(153,'530004600100070900002000074000030001060807040700060000250000100009010006004700052');
INSERT INTO sudoku_tests(id,cells) VALUES(154,'003060700000800020500207004071040600800609007002080490100508006020006000008070900');
INSERT INTO sudoku_tests(id,cells) VALUES(155,'010070600000000090030006500006150040300080002070093100002900080060000000008020010');
INSERT INTO sudoku_tests(id,cells) VALUES(156,'020000080600080003000704000007106400010090070004203900000305000800060001060000090');
INSERT INTO sudoku_tests(id,cells) VALUES(157,'000007090940000002002800076000070600500010008004060000710005800300000054050900000');
INSERT INTO sudoku_tests(id,cells) VALUES(158,'000709000750000039009302500405090302000000000201060904003801700620000013000607000');
INSERT INTO sudoku_tests(id,cells) VALUES(159,'500084000010500004060000800900030000080706090000020001002000060700009080000240003');
INSERT INTO sudoku_tests(id,cells) VALUES(160,'009080005517000000000061700190030500003008604000000000060070049402003060070006050');
?
----- 測試腳本
SET SERVEROUTPUT ON;
?
DECLARE
?? v_start_time NUMBER;
BEGIN
?? update sudoku_tests set used_time1 = NULL;
?? FOR lv_rec IN (SELECT * FROM sudoku_tests) LOOP
?????? v_start_time := dbms_utility.get_time;
?????? sudoku(lv_rec.cells);
?????? update sudoku_tests set used_time1 = dbms_utility.get_time - v_start_time where id = lv_rec.id;
?? END LOOP;
?? COMMIT;
END;
/
?
SELECT MAX(USED_TIME1)/100,MIN(USED_TIME1)/100,AVG(USED_TIME1)/100 FROM SUDOKU_TESTS;
?
?
2、sudoku.sql
?
??? <本例中所用到的思路十分樸素，之所以效果不錯，要得益于一系列標志位的設計，它們能夠快速判斷一個數字是否被用過。我注意到了對空單元格遍歷順序的改變能夠影響整個解題效率，那么在進入主循環之前能否找到一種最為高效的遍歷順序呢？或者順序根本就應該是動態的，根據取值進行調整？我作了幾個猜想都不成功，目前用的還是行，列的自然順序。希望對此有研究的朋友多多賜教，大家都把自己的算法貼出來，或者互相吹捧或者互相抬杠，樂在其中>
?
CREATE OR REPLACE TYPE t_num IS TABLE OF NUMBER
/
?
CREATE OR REPLACE TYPE type_slot AS OBJECT? (
??????????? r?????????? NUMBER
?????????? ,c?????????? NUMBER
?????????? ,cnt???????? NUMBER
?????????? ,idx???????? NUMBER
? )
/
?
CREATE OR REPLACE TYPE table_slot AS TABLE OF type_slot
/
?
CREATE OR REPLACE PROCEDURE sudoku (p_str IN VARCHAR2 DEFAULT NULL)
AS
?? TYPE t2_num IS TABLE OF t_num INDEX BY BINARY_INTEGER;
?? TYPE t3_num IS TABLE OF t2_num INDEX BY BINARY_INTEGER;
?? TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
?
?? s t_str;????? ---- 字符串數組，存放題目
?
?? ------ 三組標志位用于快速判斷某數字是否可以用于填充
?? used_c t2_num;???? --- 在此列中該數字是否已被使用
?? used_r t2_num;???? --- 在此行中該數字是否已被使用
?? used_a t2_num;???? --- 在此區中該數字是否已被使用(從上至下，從左到右劃分為9個區)
?
?? area?? t2_num;???? --- 根據行，列迅速返回所屬的區
?
??
?? slot_values t3_num;? --- 為每個單元格存放候選數字。每個坐標對應一系列標志位，如果slot_values(i)(j)(k)有值則k為i行j列的候選值
??????????????????????? --- 只對空單元有意義
??
?? v_idx? NUMBER;?????? -- 用于遍歷空單元格的指針變量
?
?? i? NUMBER;?????????? --- 臨時變量
?? j? NUMBER;
?? k? NUMBER;
?
?? empty_set? t_num := t_num(0,0,0,0,0,0,0,0,0);
?
?? empty_slots table_slot := table_slot();????? --- 存放空單元格，此數組中每個元素表示一個坐標, 以及一個指向候選值數組的指針。根據坐標及指針可到slot_values取候選值
?
?? v_continue NUMBER;
?? v_del????? NUMBER;
?
BEGIN
?? --- sample one
?? s(1):= '3 58? 176';
?? s(2):= '1?? 5?? 2';
?? s(3):= '????? 549';
?? s(4):= ' 52 986? ';
?? s(5):= '43? 12? 7';
?? s(6):= '?? 5? 4? ';
?? s(7):= '5?? 6 894';
?? s(8):= ' 69 7?? 5';
?? s(9):= '?? 9?? 61';
?
?? ---- 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
?????? IF p_str IS NOT NULL THEN
????????? s(i):= SUBSTR(p_str,(i-1)*9+1,9);
?????? END IF;
?????? used_r(i) := empty_set;??????????? ----- 初始化為未使用狀態
?????? used_c(i) := empty_set;
?????? used_a(i) := empty_set;
?????? area(i)?? := empty_set;??????????? ----- 初始化, 真正填值在下面
?
?????? FOR j IN 1..9 LOOP
?????????? area(i)(j) := (CEIL(i/3)-1)*3 + CEIL(j/3);??? -- 行列和區域的換算關系
?????????? slot_values(i)(j) := empty_set;?????????????? -- 為每個坐標賦予完整的候選數字清單
?????? END LOOP;
?? END LOOP;
?
?? FOR i IN 1..9 LOOP
?????? FOR j IN 1..9 LOOP
?????????? IF SUBSTR(s(i),j,1) BETWEEN '1' AND '9' THEN
????????????? k := TO_NUMBER(SUBSTR(s(i),j,1));
????????????? used_r(i)(k) :=1;
????????????? used_c(j)(k) :=1;
????????????? used_a(area(i)(j))(k) :=1;
?
????????????? FOR v_del IN 1..9 LOOP?????? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除。slot_values將成為稀疏數組
????????????????? slot_values(i)(v_del).DELETE(k);??
????????????????? slot_values(v_del)(j).DELETE(k);
????????????????? slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
????????????? END LOOP;
?
?????????? ELSE
????????????? ------ 發現一個未填的空單元
????????????? empty_slots.EXTEND;
????????????? empty_slots(empty_slots.COUNT) := type_slot(i,j,0,0);
?????????? END IF;
?????? END LOOP;
?? END LOOP;
?
?? v_continue :=1;
?? WHILE v_continue = 1 AND empty_slots.COUNT>0 LOOP
???????? ---- 對空單元進行篩選，如果只有一個候選數字則視為已知答案，從空單元清單中刪除
???????? v_continue := 0;
???????? v_idx := empty_slots.FIRST;
???????? WHILE v_idx IS NOT NULL LOOP
?????????????? empty_slots(v_idx).cnt := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).COUNT;? --- 這句已經沒有意義了，本來是想用它排序的但效果不好
?????????????? IF empty_slots(v_idx).cnt = 0 THEN
????????????????? RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||empty_slots(v_idx).r||','||empty_slots(v_idx).c);
?????????????? ELSIF empty_slots(v_idx).cnt = 1 THEN
????????????????? i := empty_slots(v_idx).r;
????????????????? j := empty_slots(v_idx).c;
????????????????? k := slot_values(i)(j).FIRST;
????????????????? used_r(i)(k) :=1;
????????????????? used_c(j)(k) :=1;
????????????????? used_a(area(i)(j))(k) :=1;
?
????????????????? FOR v_del IN 1..9 LOOP? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除
????????????????????? slot_values(i)(v_del).DELETE(k);
????????????????????? slot_values(v_del)(j).DELETE(k);
????????????????????? slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
????????????????? END LOOP;
?
????????????????? v_continue := 1;??? ---- 繼續循環，因為本次刪除可能導致產生新的已知單元格
????????????????? v_del := v_idx;???? ---- 本單元格已經非空，可以刪除
????????????????? s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
?????????????? ELSE
????????????????? v_del := 0;
?????????????? END IF;
?
?????????????? v_idx := empty_slots.NEXT(v_idx);? ----- 用鏈表方式進行遍歷，因為數組可能是稀疏的
?
?????????????? IF v_del>0 THEN
????????????????? empty_slots.DELETE(v_del);
?????????????? END IF;
?
???????? END LOOP;
?? END LOOP;
?
?? v_continue := 1;
?
?? IF empty_slots.COUNT>0 THEN
?????
????? ----- 借鑒小表驅動大表的思路進行排序預處理。實際應用效果不佳，此SELECT可以去掉。
????? -- SELECT CAST(MULTISET(SELECT * FROM TABLE(CAST(empty_slots AS table_slot)) ORDER BY cnt,r,c) AS table_slot)
????? --?? INTO empty_slots
????? --?? FROM DUAL;
?
????? v_idx := empty_slots.FIRST;???? --- 取第一個空單元格
????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST;? ---- 取出此位置的第一個候選值
?
????? WHILE v_idx IS NOT NULL LOOP?? ---- 遍歷所有空單元格, 主循環（最為耗時）開始
??????????? WHILE empty_slots(v_idx).idx IS NOT NULL LOOP????? ---- 遍歷此位置所有候選值, 查找可用數字
????????????????? i := empty_slots(v_idx).r;
????????????????? j := empty_slots(v_idx).c;
????????????????? k := empty_slots(v_idx).idx;??? ---- 因為我采用位圖的數據結構，位置即候選值。slot_values(i)(j)(k)存什么值無所謂，本例中恒為0
?
????????????????? IF used_c(j)(k) = 0 AND used_r(i)(k) = 0 AND used_a(area(i)(j))(k) = 0 THEN? ---- 這個值未用過
???????????????????? used_c(j)(k) := 1;
???????????????????? used_r(i)(k) := 1;
???????????????????? used_a(area(i)(j))(k) :=1;
???????????????????? EXIT;??? ---- 找到一個未用過的值，退出本循環，繼續下一個單元格
????????????????? ELSE
???????????????????? empty_slots(v_idx).idx := slot_values(i)(j).NEXT(empty_slots(v_idx).idx);? -- 用鏈表方式找下一個位置，因為數組可能是稀疏的
????????????????? END IF;
??????????? END LOOP;
?
??????????? IF empty_slots(v_idx).idx IS NULL THEN?? ---- 指針到了末尾，所有值都不可用，必須退回到上一單元格
?
?????????????? v_idx := empty_slots.PRIOR(v_idx);???? --- 退回到上一單元格
?????????????? IF v_idx IS NULL THEN????? ----- 無處可退，此題沒有答案
????????????????? v_continue := 0;
????????????????? EXIT;
?????????????? END IF;
?
?????????????? i := empty_slots(v_idx).r;????? ----- 回到上一單元格，當前值證明不行，必須釋放它并置為未用
?????????????? j := empty_slots(v_idx).c;
?????????????? k := empty_slots(v_idx).idx;
?
?????????????? used_c(j)(k) := 0;
?????????????? used_r(i)(k) := 0;
?????????????? used_a(area(i)(j))(k) :=0;
?
?????????????? empty_slots(v_idx).idx := slot_values(i)(j).NEXT(empty_slots(v_idx).idx);? -- 當前值證明不可用，繼續下一個值，下輪循環將找出下一可用值
?
??????????? ELSE
???????????? ---- 找到一個未用過的值，繼續下一個空單元格
?????????????? v_idx := empty_slots.NEXT(v_idx);
?
?????????????? IF v_idx IS NULL THEN????? ----- 所有空單元格都已處理完，答案找到了
????????????????? EXIT;
?????????????? END IF;
?????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST; ---- 取出此位置的第一個候選值
??????????? END IF;
????? END LOOP;
?
?? END IF;
?
?? IF v_continue = 1 THEN
????? v_idx := empty_slots.FIRST;
?
????? WHILE v_idx IS NOT NULL LOOP?????????? --取出空單元格里面填好的值，拼回字符串
??????????? i := empty_slots(v_idx).r;
??????????? j := empty_slots(v_idx).c;
??????????? k := empty_slots(v_idx).idx;
??????????? s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
?
??????????? v_idx := empty_slots.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;
?? ELSE
????? DBMS_OUTPUT.PUT_LINE('No Answer Found!');
?
?? END IF;
?
END sudoku;
/
?
?
3、sudoku2.sql
?
??? <這里是我的另一種嘗試，在進入主循環之前對所有空位排序。排序的原則是從最薄弱的環節開始擊破，即查找那些行、列、區中空位最少的單元。除此之外和原來的算法一樣。我到老地方下載了“高手進階”的五萬個題目，只對其中1000個進行了測試并和上一種解法作比較。一千個做下來平均0.27秒，最壞的情況是5.6秒；舊方法平均是1.15秒，最壞情況54.38秒。可見新算法有所改進。但其中也有約三分之一是舊算法更快，盡管差距不大。我在新代碼中有意使用了VARRAY, 這下子三種COLLECTION都用上了，顯得很花哨，也可當作COLLECTION應用的范例來看>
?
CREATE GLOBAL TEMPORARY TABLE sudoku_slots (
??????????? r?????????? NUMBER
?????????? ,c?????????? NUMBER?????
?????????? ,a?????????? NUMBER?????
?????????? ,cnt???????? NUMBER
?????????? ,idx???????? NUMBER
?????????? ,sort_order? NUMBER
? ) ON COMMIT PRESERVE ROWS
/
?
CREATE OR REPLACE PROCEDURE sudoku2(p_str IN VARCHAR2 DEFAULT NULL)
AS
?? TYPE t_num IS TABLE OF NUMBER;
?
?? TYPE t2_num IS VARRAY(9) OF t_num;
?? TYPE t3_num IS VARRAY(9) OF t2_num;
??
?? TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
?
?? s t_str;????? ---- 字符串數組，存放題目
?
?? ------ 三組標志位用于快速判斷某數字是否可以用于填充
?? used_c t2_num := t2_num();???? --- 在此列中該數字是否已被使用
?? used_r t2_num := t2_num();???? --- 在此列中該數字是否已被使用
?? used_a t2_num := t2_num();???? --- 在此區中該數字是否已被使用(從上至下，從左到右劃分為9個區)
?
?? area?? t2_num := t2_num();???? --- 根據行，列迅速返回所屬的區
?
??
?? slot_values t3_num := t3_num();? --- 為每個單元格存放候選數字。每個坐標對應一系列標志位，如果slot_values(i)(j)(k)有值則k為i行j列的候選值
??????????????????????? --- 只對空單元有意義
??
?? v_idx? NUMBER;?????? -- 用于遍歷空單元格的指針變量
?
?? i? NUMBER;?????????? --- 臨時變量
?? j? NUMBER;
?? k? NUMBER;
?
?? empty_set? t_num := t_num(0,0,0,0,0,0,0,0,0);
?
?? TYPE t_sudoku_slots IS TABLE OF sudoku_slots%ROWTYPE;
?? empty_slots t_sudoku_slots;??? --- 存放空單元格，此數組中每個元素表示一個坐標, 以及一個指向候選值數組的指針。根據坐標及指針可到slot_values取候選值
??
?? v_continue NUMBER;
?
BEGIN
?
/*
?? ---- 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 ' ;
?
?? --- sample one
?? s(1):= '3 58? 176';
?? s(2):= '1?? 5?? 2';
?? s(3):= '????? 549';
?? s(4):= ' 52 986? ';
?? s(5):= '43? 12? 7';
?? s(6):= '?? 5? 4? ';
?? s(7):= '5?? 6 894';
?? s(8):= ' 69 7?? 5';
?? s(9):= '?? 9?? 61';
*/
?
?? --- 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? ' ;
?
?? used_r.EXTEND(9);????? ----- 對VARRAY數組進行初始化
?? used_c.EXTEND(9);
?? used_a.EXTEND(9);
?? area.EXTEND(9);
?? slot_values.EXTEND(9);? ----- 對VARRAY數組(第一維)進行初始化
??
?? FOR i IN 1..9 LOOP
?????? IF p_str IS NOT NULL THEN
????????? s(i):= SUBSTR(p_str,(i-1)*9+1,9);
?????? END IF;
?????? used_r(i) := empty_set;??????????? ----- 初始化為未使用狀態
?????? used_c(i) := empty_set;
?????? used_a(i) := empty_set;
?
?????? area(i)?? := empty_set;??????????? ----- 初始化, 真正填值在下面
?
?????? slot_values(i) := t2_num();????? ----- 對VARRAY數組(第二維)進行初始化
?????? slot_values(i).EXTEND(9);
?????? FOR j IN 1..9 LOOP
?????????? area(i)(j) := (CEIL(i/3)-1)*3 + CEIL(j/3);??? -- 行列和區域的換算關系
?????????? slot_values(i)(j) := empty_set;?????????????? -- 為每個坐標賦予完整的候選數字清單
?????? END LOOP;
?? END LOOP;
??
?? DELETE sudoku_slots;
??
?? FOR i IN 1..9 LOOP
?????? FOR j IN 1..9 LOOP
?????????? IF SUBSTR(s(i),j,1) BETWEEN '1' AND '9' THEN
????????????? k := TO_NUMBER(SUBSTR(s(i),j,1));
????????????? used_r(i)(k) :=1;
????????????? used_c(j)(k) :=1;
????????????? used_a(area(i)(j))(k) :=1;
?????????????
????????????? FOR v_del IN 1..9 LOOP?????? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除。slot_values將成為稀疏數組
????????????????? slot_values(i)(v_del).DELETE(k);
????????????????? slot_values(v_del)(j).DELETE(k);
????????????????? slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
????????????? END LOOP;
?
?????????? ELSE
????????????? ------ 發現一個未填的空單元
????????????? INSERT INTO sudoku_slots (r,c,a) VALUES (i,j,area(i)(j));
?
?????????? END IF;
?????? END LOOP;
?? END LOOP;
?
?? v_continue :=1;
?? WHILE v_continue = 1 LOOP
???????? ---- 對空單元進行篩選，如果只有一個候選數字則視為已知答案，從空單元清單中刪除
?
???????? v_continue := 0;
????????
???????? FOR lv_rec IN (SELECT * FROM sudoku_slots) LOOP
???????????? v_idx := slot_values(lv_rec.r)(lv_rec.c).COUNT;
?????????????? IF v_idx = 0 THEN
????????????????? RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||lv_rec.r||','||lv_rec.c);
?????????????? ELSIF v_idx = 1 THEN
????????????????? i := lv_rec.r;
????????????????? j := lv_rec.c;
????????????????? k := slot_values(i)(j).FIRST;
????????????????? used_r(i)(k) :=1;
????????????????? used_c(j)(k) :=1;
????????????????? used_a(area(i)(j))(k) :=1;
?????????????????
????????????????? FOR v_del IN 1..9 LOOP? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除
????????????????????? slot_values(i)(v_del).DELETE(k);
????????????????????? slot_values(v_del)(j).DELETE(k);
????????????????????? slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
????????????????? END LOOP;
?????????????????
????????????????? v_continue := 1;??? ---- 繼續循環，因為本次刪除可能導致產生新的已知單元格
????????????????? s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
?????????????????
????????????????? DELETE sudoku_slots WHERE r=lv_rec.r AND c=lv_rec.c; ---- 本單元格已經非空，可以刪除
?????????????? ELSE
????????????????? UPDATE sudoku_slots SET cnt = v_idx WHERE r=lv_rec.r AND c=lv_rec.c;
?????????????? END IF;
??????????????
???????? END LOOP;
?? END LOOP;
?
?? v_continue := 1;
?
?? v_idx := 0;
?? ---- 對空單元格進行排序。排序原則是優先取所在的行、列、區空位最少的單元
?? WHILE v_continue >0 LOOP
???????? v_continue := 0;
?
???????? FOR lv_rec IN (SELECT r,c,a
????????????????????????????? ,LEAST(r_cnt,c_cnt,a_cnt) AS cnt1
????????????????????????????? ,r_cnt+c_cnt+a_cnt cnt2
????????????????????????????? ,cnt
???????????????????????? FROM (SELECT r,c,a,cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY r) AS r_cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY c) AS c_cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY a) AS a_cnt
???????????????????????????????? FROM sudoku_slots
??????????????????????????????? WHERE sort_order IS NULL
??????????????????????????????? )
??????????????????????? ORDER BY cnt1,cnt2,cnt
??????????????????????? )
???????? LOOP
???????????? v_idx := v_idx +1;
???????????? UPDATE sudoku_slots SET sort_order = v_idx WHERE r=lv_rec.r AND c=lv_rec.c;
???????????? v_continue := 1;
??
???????????? EXIT;
???????? END LOOP;
?
?? END LOOP;
?
?? ---- 把排好序的數據載入內存數組
?? SELECT *
???? BULK COLLECT INTO empty_slots
???? FROM sudoku_slots
???? ORDER BY sort_order;
?
?? v_continue := 1;
??
?? IF empty_slots.COUNT>0 THEN
?
????? v_idx := 1;???? --- 取第一個空單元格
????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST;? ---- 取出此位置的第一個候選值
?
????? WHILE v_idx <= empty_slots.COUNT LOOP?? ---- 遍歷所有空單元格, 主循環（最為耗時）開始
??????????? WHILE empty_slots(v_idx).idx IS NOT NULL LOOP????? ---- 遍歷此位置所有候選值, 查找可用數字
????????????????? i := empty_slots(v_idx).r;
????????????????? j := empty_slots(v_idx).c;
????????????????? k := empty_slots(v_idx).idx;??? ---- 因為我采用位圖的數據結構，位置即候選值。slot_values(i)(j)(k)存什么值無所謂，本例中恒為0
?
????????????????? IF used_c(j)(k) = 0 AND used_r(i)(k) = 0 AND used_a(area(i)(j))(k) = 0 THEN? ---- 這個值未用過
???????????????????? used_c(j)(k) := 1;
???????????????????? used_r(i)(k) := 1;
???????????????????? used_a(area(i)(j))(k) :=1;
???????????????????? EXIT;??? ---- 找到一個未用過的值，退出本循環，繼續下一個單元格
????????????????? ELSE
???????????????????? empty_slots(v_idx).idx := slot_values(i)(j).NEXT(empty_slots(v_idx).idx);? -- 用鏈表方式找下一個位置，因為數組可能是稀疏的
????????????????? END IF;
??????????? END LOOP;
?
??????????? IF empty_slots(v_idx).idx IS NULL THEN?? ---- 指針到了末尾，所有值都不可用，必須退回到上一單元格
?
?????????????? v_idx := v_idx-1;???? --- 退回到上一單元格
?????????????? IF v_idx =0 THEN????? ----- 無處可退，此題沒有答案
????????????????? v_continue := 0;
????????????????? EXIT;
?????????????? END IF;
?
?????????????? i := empty_slots(v_idx).r;????? ----- 回到上一單元格，當前值證明不行，必須釋放它并置為未用
?????????????? j := empty_slots(v_idx).c;
?????????????? k := empty_slots(v_idx).idx;
?
?????????????? used_c(j)(k) := 0;
?????????????? used_r(i)(k) := 0;
?????????????? used_a(area(i)(j))(k) :=0;
?
?????????????? empty_slots(v_idx).idx := slot_values(i)(j).NEXT(empty_slots(v_idx).idx);? -- 當前值證明不可用，繼續下一個值，下輪循環將找出下一可用值
?
??????????? ELSE
???????????? ---- 找到一個未用過的值，繼續下一個空單元格
?????????????? v_idx := v_idx+1;
?
?????????????? IF v_idx >empty_slots.COUNT THEN????? ----- 所有空單元格都已處理完，答案找到了
????????????????? EXIT;
?????????????? END IF;
?????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST; ---- 取出此位置的第一個候選值
??????????? END IF;
????? END LOOP;
?
?? END IF;
?
?? IF v_continue = 1 THEN
?
????? FOR v_idx IN 1..empty_slots.COUNT LOOP?????????? --取出空單元格里面填好的值，拼回字符串
??????????? i := empty_slots(v_idx).r;
??????????? j := empty_slots(v_idx).c;
??????????? k := empty_slots(v_idx).idx;
??????????? s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
?
????? END LOOP;
?
????? DBMS_OUTPUT.PUT_LINE('Answer Found:');
????? FOR i IN 1..9 LOOP? ------ 輸出答案
????????? DBMS_OUTPUT.PUT_LINE(s(i));
????? END LOOP;
?? ELSE
????? DBMS_OUTPUT.PUT_LINE('No Answer Found!');
?
?? END IF;
?
END;
/
?
?
4、sudoku3.sql
?
??? <第三種嘗試：放棄前面用的標志位方法，為每個空位設置一個候選值數組。此方法的優勢是不需要判斷，有值就肯定是未用過的；代價就是每當用了一個值，必須從后續節點的候選值（可用值數組）刪除它。另一好處就是當要刪除時如果發現此值是唯一的，則可以快速斷定該值不可用。實際效果：1000個題目的平均用時從0.27減少為0.17秒>
?
CREATE GLOBAL TEMPORARY TABLE sudoku_slots (
??????????? r?????????? NUMBER
?????????? ,c?????????? NUMBER?????
?????????? ,a?????????? NUMBER?????
?????????? ,cnt???????? NUMBER
?????????? ,idx???????? NUMBER
?????????? ,sort_order? NUMBER
? ) ON COMMIT PRESERVE ROWS
/
?
CREATE OR REPLACE PROCEDURE sudoku3(p_str IN VARCHAR2 DEFAULT NULL)
AS
?? TYPE t_num IS TABLE OF NUMBER;
?
?? TYPE t2_num IS VARRAY(9) OF t_num;
?? TYPE t3_num IS VARRAY(9) OF t2_num;
??
?? TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
?
?? s t_str;????? ---- 字符串數組，存放題目
?
??
?? slot_values t3_num := t3_num();? --- 為每個單元格存放候選數字。每個坐標對應一系列標志位，如果slot_values(i)(j)(k)有值則k為i行j列的候選值
??????????????????????? --- 只對空單元有意義
??
?? v_idx? NUMBER;?????? -- 用于遍歷空單元格的指針變量
?
?? i? NUMBER;?????????? --- 臨時變量
?? j? NUMBER;
?? k? NUMBER;
?
?? empty_set? t_num := t_num(0,0,0,0,0,0,0,0,0);
?
?? TYPE t_sudoku_slots IS TABLE OF sudoku_slots%ROWTYPE;
?? empty_slots t_sudoku_slots;??? --- 存放空單元格，此數組中每個元素表示一個坐標, 以及一個指向候選值數組的指針。根據坐標及指針可到slot_values取候選值
??
?? v_continue NUMBER;
?
?? deleted_by t3_num := t3_num(); ----如果某單元的某值被它的上級刪除，則這里存放著上級單元的編號
?
?? TYPE t_ptr IS TABLE OF t_sudoku_slots INDEX BY BINARY_INTEGER;
?
?? pointers t_ptr;????? --- 對應于empty_slots中的每個空單元格，這組指針指向其后續空位，而且和本節點是處于同一行或列或區的
??????????????????????? --- 當這個空位取某個值時，用這組指針可以快速將該值從后續的候選單中刪除。
??
?? lv_badvalue NUMBER;
BEGIN
?
/*
?? ---- 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 ' ;
?
?? --- sample one
?? s(1):= '3 58? 176';
?? s(2):= '1?? 5?? 2';
?? s(3):= '????? 549';
?? s(4):= ' 52 986? ';
?? s(5):= '43? 12? 7';
?? s(6):= '?? 5? 4? ';
?? s(7):= '5?? 6 894';
?? s(8):= ' 69 7?? 5';
?? s(9):= '?? 9?? 61';
*/
?
?? --- 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? ' ;
?
?? slot_values.EXTEND(9);? ----- 對VARRAY數組(第一維)進行初始化
?
?? FOR i IN 1..9 LOOP
?????? IF p_str IS NOT NULL THEN
????????? s(i):= SUBSTR(p_str,(i-1)*9+1,9);
?????? END IF;
?
?????? slot_values(i) := t2_num();????? ----- 對VARRAY數組(第二維)進行初始化
?????? slot_values(i).EXTEND(9);
?????? FOR j IN 1..9 LOOP
?????????? slot_values(i)(j) := empty_set;?????????????? -- 為每個坐標賦予完整的候選數字清單
?????? END LOOP;
?? END LOOP;
??
?
?? DELETE sudoku_slots;
??
?? FOR i IN 1..9 LOOP
?????? FOR j IN 1..9 LOOP
?????????? IF SUBSTR(s(i),j,1) BETWEEN '1' AND '9' THEN
????????????? k := TO_NUMBER(SUBSTR(s(i),j,1));
?????????????
????????????? FOR v_del IN 1..9 LOOP?????? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除。slot_values將成為稀疏數組
????????????????? slot_values(i)(v_del).DELETE(k);
????????????????? slot_values(v_del)(j).DELETE(k);
????????????????? slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
????????????? END LOOP;
?
?????????? ELSE
????????????? ------ 發現一個未填的空單元
????????????? INSERT INTO sudoku_slots (r,c,a) VALUES (i,j,(CEIL(i/3)-1)*3 + CEIL(j/3));
?
?????????? END IF;
?????? END LOOP;
?? END LOOP;
?
?? v_continue :=1;
?? WHILE v_continue = 1 LOOP
???????? ---- 對空單元進行篩選，如果只有一個候選數字則視為已知答案，從空單元清單中刪除
?
???????? v_continue := 0;
????????
???????? FOR lv_rec IN (SELECT * FROM sudoku_slots) LOOP
???????????? v_idx := slot_values(lv_rec.r)(lv_rec.c).COUNT;
?????????????? IF v_idx = 0 THEN
????????????????? RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||lv_rec.r||','||lv_rec.c);
?????????????? ELSIF v_idx = 1 THEN
????????????????? i := lv_rec.r;
????????????????? j := lv_rec.c;
????????????????? k := slot_values(i)(j).FIRST;
?????????????????
????????????????? FOR v_del IN 1..9 LOOP? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除
????????????????????? slot_values(i)(v_del).DELETE(k);
????????????????????? slot_values(v_del)(j).DELETE(k);
????????????????????? slot_values((CEIL(i/3)-1)*3+CEIL(v_del/3))((CEIL(j/3)-1)*3+MOD(v_del-1,3)+1).DELETE(k);
????????????????? END LOOP;
?????????????????
????????????????? v_continue := 1;??? ---- 繼續循環，因為本次刪除可能導致產生新的已知單元格
????????????????? s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
?????????????????
????????????????? DELETE sudoku_slots WHERE r=lv_rec.r AND c=lv_rec.c; ---- 本單元格已經非空，可以刪除
?????????????? ELSE
????????????????? UPDATE sudoku_slots SET cnt = v_idx WHERE r=lv_rec.r AND c=lv_rec.c;
?????????????? END IF;
??????????????
???????? END LOOP;
?? END LOOP;
?
?? v_continue := 1;
?
?? v_idx := 0;
?
?? deleted_by := slot_values;???? ---- 初始化為零
?
?? ---- 對空單元格進行排序。排序原則是優先取所在的行、列、區空位最少的單元
?? WHILE v_continue >0 LOOP
???????? v_continue := 0;
?
???????? FOR lv_rec IN (SELECT r,c,a
????????????????????????????? ,LEAST(r_cnt,c_cnt,a_cnt) AS cnt1
????????????????????????????? ,r_cnt+c_cnt+a_cnt cnt2
????????????????????????????? ,cnt
???????????????????????? FROM (SELECT r,c,a,cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY r) AS r_cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY c) AS c_cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY a) AS a_cnt
???????????????????????????????? FROM sudoku_slots
??????????????????????????????? WHERE sort_order IS NULL
??????????????????????????????? )
??????????????????????? ORDER BY cnt1,cnt2,cnt--,r,c
??????????????????????? )
???????? LOOP
???????????? v_idx := v_idx +1;
???????????? UPDATE sudoku_slots SET sort_order = v_idx WHERE r=lv_rec.r AND c=lv_rec.c;
???????????? v_continue := 1;
????????????
???????????? FOR i IN 1..9 LOOP
???????????????? IF NOT slot_values(lv_rec.r)(lv_rec.c).EXISTS(i) THEN
??????????????????? deleted_by(lv_rec.r)(lv_rec.c)(i) := NULL;?????????? ----- 如果本來沒有候選值則置為NULL
???????????????? END IF;
???????????? END LOOP;
?
???????????? SELECT *??? ------ 一組指針，指向本空位后續的空位，它們和本空格位于同一行或列或區
????????????? BULK COLLECT INTO pointers(v_idx)
????????????? FROM sudoku_slots
???????????? WHERE sort_order IS NULL???? ----- sort_order為空表示后續的空位, 前面的都有值了
?????????????????? AND (r = lv_rec.r OR c = lv_rec.c OR a=lv_rec.a);
????????????
???????????? EXIT;
???????? END LOOP;
?
?? END LOOP;
?
?? ---- 把排好序的數據載入內存數組
?? SELECT *
???? BULK COLLECT INTO empty_slots
???? FROM sudoku_slots
???? ORDER BY sort_order;
?
?? v_continue := 1;
??
?? IF empty_slots.COUNT>0 THEN
?
????? v_idx := 1;???? --- 取第一個空單元格
????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST;? ---- 取出此位置的第一個候選值
?
????? WHILE v_idx <= empty_slots.COUNT LOOP?? ---- 遍歷所有空單元格, 主循環（最為耗時）開始
??????????? IF empty_slots(v_idx).idx IS NOT NULL THEN?????
?????????????? k := empty_slots(v_idx).idx;??? ---- 因為我采用位圖的數據結構，位置即候選值。slot_values(i)(j)(k)存什么值無所謂，本例中恒為0
?????????????????
?????????????? lv_badvalue :=0;
?
?????????????? FOR v_del IN 1..pointers(v_idx).COUNT LOOP? ---- 把數字K從后續單元格的候選清單中刪除
?????????????????? IF slot_values(pointers(v_idx)(v_del).r)(pointers(v_idx)(v_del).c).EXISTS(k) THEN???? --- 該位置有值，必須刪除
????????????????????? IF slot_values(pointers(v_idx)(v_del).r)(pointers(v_idx)(v_del).c).COUNT=1 THEN??? -- 只剩下唯一一個值，不可刪除. 說明當前值K是不可行的
???????????????????????? FOR i IN 1..v_del-1 LOOP??? ---- 把前面已刪的補回去
???????????????????????????? IF deleted_by(pointers(v_idx)(i).r)(pointers(v_idx)(i).c)(k) = v_idx THEN
??????????????????????????????? slot_values(pointers(v_idx)(i).r)(pointers(v_idx)(i).c)(k) :=0;
???????????????????????????? END IF;
???????????????????????? END LOOP;
???????????????????????? lv_badvalue :=1;??????? --- 標志位說明K不可用
???????????????????????? EXIT;
????????????????????? ELSE
???????????????????????? slot_values(pointers(v_idx)(v_del).r)(pointers(v_idx)(v_del).c).DELETE(k);???? -- 候選值多于一個，所以可把K剔除
???????????????????????? deleted_by(pointers(v_idx)(v_del).r)(pointers(v_idx)(v_del).c)(k) := v_idx;??? -- 此標記表明K是被v_idx節點刪除的
????????????????????? END IF;
?????????????????????
?????????????????? END IF;
?????????????? END LOOP;
?
?????????????? IF lv_badvalue =0 THEN
?
????????????????? v_idx := v_idx+1;??? ---- 找到一個未用過的值，繼續下一個空單元格
?????
????????????????? IF v_idx >empty_slots.COUNT THEN????? ----- 所有空單元格都已處理完，答案找到了
???????????????????? EXIT;
????????????????? END IF;
????????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST; ---- 取出新位置的第一個候選值
?????????????? ELSE
????????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).NEXT(k);? -- 當前值證明不可用，繼續下一個值，下輪循環將找出下一可用值
?????????????? END IF;
?
??????????? ELSE??? ---- 指針到了末尾，所有值都不可用，必須退回到上一單元格
?
?????????????? v_idx := v_idx-1;???? --- 退回到上一單元格
?????????????? IF v_idx =0 THEN????? ----- 無處可退，此題沒有答案
????????????????? v_continue := 0;
????????????????? EXIT;
?????????????? END IF;
?
?????????????? ----- 回到上一單元格，當前值證明不行，必須釋放它并置為未用
?????????????? k := empty_slots(v_idx).idx;
?
?????????????? FOR v_del IN 1..pointers(v_idx).COUNT LOOP? ---- 把數字K加回候選單
?????????????????? IF deleted_by(pointers(v_idx)(v_del).r)(pointers(v_idx)(v_del).c)(k) = v_idx THEN???? -- 此值是被當前空位所刪除的，必須加回去
????????????????????? slot_values(pointers(v_idx)(v_del).r)(pointers(v_idx)(v_del).c)(k) :=0;
?????????????????? END IF;
?
?????????????? END LOOP;
?
?????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).NEXT(k);? -- 當前值證明不可用，繼續下一個值，下輪循環將找出下一可用值
?
??????????? END IF;
????? END LOOP;
?
?? END IF;
?
?? IF v_continue = 1 THEN
?
????? FOR v_idx IN 1..empty_slots.COUNT LOOP?????????? --取出空單元格里面填好的值，拼回字符串
??????????? i := empty_slots(v_idx).r;
??????????? j := empty_slots(v_idx).c;
??????????? k := empty_slots(v_idx).idx;
??????????? s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
?
????? END LOOP;
?
????? DBMS_OUTPUT.PUT_LINE('Answer Found:');
????? FOR i IN 1..9 LOOP? ------ 輸出答案
????????? DBMS_OUTPUT.PUT_LINE(s(i));
????? END LOOP;
?? ELSE
????? DBMS_OUTPUT.PUT_LINE('No Answer Found!');
?
?? END IF;
?
END;
/
?
?
5、sudoku5.sql
?
??? <五毒俱全的算法程序>
?
?
CREATE GLOBAL TEMPORARY TABLE sudoku_slots (
??????????? r?????????? NUMBER
?????????? ,c?????????? NUMBER?????
?????????? ,a?????????? NUMBER?????
?????????? ,cnt???????? NUMBER
?????????? ,idx???????? NUMBER
?????????? ,sort_order? NUMBER
?????????? ,s_type????? NUMBER
?????????? ,s_type2???? NUMBER
?????????? ,extra_rule? NUMBER
? ) ON COMMIT PRESERVE ROWS
/
?
CREATE OR REPLACE PROCEDURE sudoku5(p_str IN VARCHAR2 DEFAULT NULL)
AS
?? TYPE t_num IS TABLE OF NUMBER;
?
?? TYPE t2_num IS VARRAY(21) OF t_num;
?? TYPE t3_num IS VARRAY(21) OF t2_num;
??
?? TYPE t_str IS TABLE OF VARCHAR2(30) INDEX BY BINARY_INTEGER;
?
?? s t_str;????? ---- 字符串數組，存放題目
?
?? slot_values t3_num := t3_num();? --- 為每個單元格存放候選數字。每個坐標對應一系列標志位，如果slot_values(i)(j)(k)有值則k為i行j列的候選值
??????????????????????? --- 只對空單元有意義
??
?? v_idx? NUMBER;?????? -- 用于遍歷空單元格的指針變量
?
?? i? NUMBER;?????????? --- 臨時變量
?? j? NUMBER;
?? k? NUMBER;
?
?? empty_set? t_num := t_num(0,0,0,0,0,0,0,0,0);
?
?? TYPE t_sudoku_slots IS TABLE OF sudoku_slots%ROWTYPE;
?? empty_slots t_sudoku_slots;??? --- 存放空單元格，此數組中每個元素表示一個坐標, 以及一個指向候選值數組的指針。根據坐標及指針可到slot_values取候選值
??
?? v_continue NUMBER;
?
?? deleted_by t3_num := t3_num(); ----如果某單元的某值被它的上級刪除，則這里存放著上級單元的編號
?
?? TYPE t_ptr IS TABLE OF t_sudoku_slots INDEX BY BINARY_INTEGER;
?
?? pointers t_ptr;????? --- 對應于empty_slots中的每個空單元格，這組指針指向其后續空位，而且和本節點是處于同一行或列或區的
??????????????????????? --- 當這個空位取某個值時，用這組指針可以快速將該值從后續的候選單中刪除。
?
?? lv_badvalue NUMBER;
??
?? k2 NUMBER;
?
?? PROCEDURE cleanout_value_regular (r number,c number, k number, r_offset number, c_offset number)
?? AS
?? BEGIN
???? ----- 標準數獨，把已知值從其它格子的候選值清單中清除
???? FOR v_del IN 1..9 LOOP?????? ---- 把數字K從本列、本行、本區域中所有單元格的候選清單中刪除。slot_values將成為稀疏數組
???????? slot_values(r)(v_del+c_offset).DELETE(k);
???????? slot_values(v_del+r_offset)(c).DELETE(k);
???????? slot_values((CEIL((r-r_offset)/3)-1)*3+CEIL(v_del/3)+r_offset)((CEIL((c-c_offset)/3)-1)*3+MOD(v_del-1,3)+1+c_offset).DELETE(k);
???? END LOOP;
??
?? END cleanout_value_regular;
?
?? PROCEDURE cleanout_value_seq (r number,c number, k number, r_offset number, c_offset number)
?? AS
?? BEGIN
???? ------ 左上角的連續數獨，從上下左右的鄰居中清除連續數
???? IF r BETWEEN 1+r_offset AND 9+r_offset AND c BETWEEN 1+c_offset AND 9+c_offset THEN
??????? slot_values(r)(c).DELETE(CASE WHEN k=1 THEN 9 ELSE k-1 END);
??????? slot_values(r)(c).DELETE(CASE WHEN k=9 THEN 1 ELSE k+1 END);
???? END IF;
?? END cleanout_value_seq;
?
?? PROCEDURE cleanout_value_horse (r number,c number, k number, r_offset number, c_offset number)
?? AS
?? BEGIN
???? ----左下角的馬步數獨，從馬步格子中的候選值清單中刪除已知數
???? IF r BETWEEN 1+r_offset AND 9+r_offset AND c BETWEEN 1+c_offset AND 9+c_offset THEN
??????? slot_values(r)(c).DELETE(k);
???? END IF;
?? END cleanout_value_horse;
?
?? PROCEDURE cleanout_value_border (r number,c number, k number, r_offset number, c_offset number, a number)
?? AS
?? BEGIN
???? ------ 右下角的邊界數獨，上下左右的鄰居如果處于不同區域中（邊界）則刪除同為合/素數的候選數字
???? IF r BETWEEN 1+r_offset AND 9+r_offset AND c BETWEEN 1+c_offset AND 9+c_offset AND (CEIL(r/3)-1)*3 + CEIL(c/3)<>a THEN
??????? IF k IN (2,3,5,7) THEN
?????????? slot_values(r)(c).DELETE(2);
?????????? slot_values(r)(c).DELETE(3);
?????????? slot_values(r)(c).DELETE(5);
?????????? slot_values(r)(c).DELETE(7);
??????? ELSE
?????????? slot_values(r)(c).DELETE(4);
?????????? slot_values(r)(c).DELETE(6);
?????????? slot_values(r)(c).DELETE(8);
?????????? slot_values(r)(c).DELETE(9);
??????? END IF;
???????
???? END IF;
?? END cleanout_value_border;
?
??
?? PROCEDURE cleanout_value (r number,c number, k number)
?? AS
????? a NUMBER;
?? BEGIN
????? --- 在位置r,c有已知值k, 將k從其它格子的候選值清單中清除。
????? IF r BETWEEN 1 AND 9 AND c BETWEEN 1 AND 9 THEN??????????? ----- 左上角:不連續數獨
???????? cleanout_value_regular(r,c,k,0,0);
?
???????? -- 要求上下左右相鄰的格之間的數字不連續，另外1的相鄰數為2和9，9的相鄰數為8和1 。
???????? cleanout_value_seq(r-1,c,k,0,0);
???????? cleanout_value_seq(r+1,c,k,0,0);
???????? cleanout_value_seq(r,c-1,k,0,0);
???????? cleanout_value_seq(r,c+1,k,0,0);
????????
????? END IF;
?
????? IF r BETWEEN 1 AND 9 AND c BETWEEN 13 AND 21 THEN??????????? ----- 右上角:無緣數獨
???????? cleanout_value_regular(r,c,k,0,12);
?
???????? -- 要求每個格子中的數字與其相鄰（包括斜線）的八個格子中的數字都不能相同。
???????? FOR i IN GREATEST(r-1,1)..LEAST(r+1,9) LOOP
???????????? FOR j IN GREATEST(c-1,13)..LEAST(c+1,21) LOOP
???????????????? IF i<>r OR j<>c THEN
??????????????????? slot_values(i)(j).DELETE(k);
???????????????? END IF;
???????????? END LOOP;
???????? END LOOP;
????????
????? END IF;
?
????? IF r BETWEEN 7 AND 15 AND c BETWEEN 7 AND 15 THEN??????????? ----- 中? 部:標準數獨
???????? cleanout_value_regular(r,c,k,6,6);
????? END IF;
?
????? IF r BETWEEN 13 AND 21 AND c BETWEEN 1 AND 9 THEN??????????? ----- 左下角:無馬數獨
???????? cleanout_value_regular(r,c,k,12,0);
?
???????? --要求每個格子中的數字與其成馬步（前進二拐一）的八個格子中的數字都不能相同。
???????? cleanout_value_horse(r-2,c-1,k,12,0);
???????? cleanout_value_horse(r-2,c+1,k,12,0);
???????? cleanout_value_horse(r+2,c-1,k,12,0);
???????? cleanout_value_horse(r+2,c+1,k,12,0);
???????? cleanout_value_horse(r-1,c-2,k,12,0);
???????? cleanout_value_horse(r-1,c+2,k,12,0);
???????? cleanout_value_horse(r+1,c-2,k,12,0);
???????? cleanout_value_horse(r+1,c+2,k,12,0);
???????????
????? END IF;
?
????? IF r BETWEEN 13 AND 21 AND c BETWEEN 13 AND 21 THEN??????????? ----- 右下角:邊界數獨
???????? cleanout_value_regular(r,c,k,12,12);
?
???????? -- 要求任意兩個相鄰的九宮格的邊界部位，不能同為質數（2、3、5、7）或同為合數（4、6、8、9），只能是不同類的數相連（行或列），1既不是質數也不是合數，可與任何數相連。???
????????
???????? IF k<>1 THEN
??????????? a :=? (CEIL(r/3)-1)*3 + CEIL(c/3);???????? ----- 根據行列坐標換算所處區域, 用于判斷是否邊界
??????????? cleanout_value_border(r-1,c,k,12,12,a);
??????????? cleanout_value_border(r+1,c,k,12,12,a);
??????????? cleanout_value_border(r,c-1,k,12,12,a);
??????????? cleanout_value_border(r,c+1,k,12,12,a);
???????? END IF;
????? END IF;
???
???
?? END cleanout_value;
?
?? PROCEDURE remove_value (r NUMBER,c NUMBER,k NUMBER, deleted_by_idx NUMBER, p_bad_value IN OUT NUMBER)
?? IS
?? BEGIN
????? --- 從位置r,c的候選值清單中刪除值k
????? IF p_bad_value = 1 THEN
???????? RETURN;
????? END IF;
?????
????? IF slot_values(r)(c).EXISTS(k) THEN???? --- 該位置有值
???????? IF slot_values(r)(c).COUNT=1 THEN??? -- 只剩下唯一一個值，不可刪除. 說明當前值K是不可行的
??????????? p_bad_value := 1;
??????????? RETURN;
???????? ELSE
??????????? slot_values(r)(c).DELETE(k);???? -- 候選值多于一個，所以可把K剔除
??????????? deleted_by(r)(c)(k) := deleted_by_idx;??? -- 此標記表明K是被v_idx節點刪除的
???????? END IF;
????????
????? END IF;
?????
????? RETURN;
?? END remove_value;
?
?? PROCEDURE add_value_back (r NUMBER,c NUMBER,k NUMBER, deleted_by_idx NUMBER)
?? IS
?? BEGIN
????? ---- 如果位置r,c上的數字k是由前面空格deleted_by_idx刪除的，則加回候選清單
????? IF deleted_by(r)(c)(k) = deleted_by_idx THEN
???????? slot_values(r)(c)(k) :=0;
????? END IF;
?
?? END add_value_back;
?
?? PROCEDURE restore_deleted_value (r NUMBER,c NUMBER,k NUMBER, deleted_by_idx NUMBER, p_extra_rule NUMBER, p_s_type NUMBER)
?? AS
?? BEGIN
????? add_value_back(r,c,k,deleted_by_idx);
????? IF p_extra_rule=1 THEN
???????? IF p_s_type=1 THEN???? ---- 左上角的連續數獨，補回被刪除額外的數（連續值）
??????????? add_value_back(r,c,(CASE WHEN k=1 THEN 9 ELSE k-1 END),deleted_by_idx);
??????????? add_value_back(r,c,(CASE WHEN k=9 THEN 1 ELSE k+1 END),deleted_by_idx);
???????? ELSIF k<>1 THEN? ------ 右下角的邊界數獨，補回被刪除額外的數（同為合/素數）
???????????? IF k IN (2,3,5,7) THEN
??????????????? add_value_back(r,c,2,deleted_by_idx);
??????????????? add_value_back(r,c,3,deleted_by_idx);
??????????????? add_value_back(r,c,5,deleted_by_idx);
??????????????? add_value_back(r,c,7,deleted_by_idx);
???????????? ELSE
??????????????? add_value_back(r,c,4,deleted_by_idx);
??????????????? add_value_back(r,c,6,deleted_by_idx);
??????????????? add_value_back(r,c,8,deleted_by_idx);
??????????????? add_value_back(r,c,9,deleted_by_idx);
???????????? END IF;
???????? END IF;???????
????? END IF;
?????
?? END restore_deleted_value;
??
BEGIN
?
?? --- sample
?? s( 1):= ' 8????? 3***2????? 8 ' ;
?? s( 2):= '9 41?? 8 *** 7?? 34 2' ;
?? s( 3):= ' 3? 5??? ***??? 2? 6 ' ;
?? s( 4):= ' 7? 286? ***? 519? 7 ' ;
?? s( 5):= '? 63?? 5 *** 9?? 81? ' ;
?? s( 6):= '?? 6?? 3 *** 3?? 2?? ' ;
?? s( 7):= '?? 9?? 7???? 4?? 1?? ' ;
?? s( 8):= ' 4? 135?? 4?? 783? 5 ' ;
?? s( 9):= '3???????? 2???????? 4' ;
?? s(10):= '******?? 5 9?? ******' ;
?? s(11):= '****** 52?? 79 ******' ;
?? s(12):= '******?? 8 2?? ******' ;
?? s(13):= '7???????? 5???????? 4' ;
?? s(14):= ' 2? 694?? 6?? 954? 1 ' ;
?? s(15):= '?? 5?? 1???? 5?? 1?? ' ;
?? s(16):= '?? 4?? 2 *** 4?? 5?? ' ;
?? s(17):= '? 29?? 3 *** 6?? 41? ' ;
?? s(18):= ' 6? 159? ***? 873? 4 ' ;
?? s(19):= ' 9? 4??? ***??? 9? 5 ' ;
?? s(20):= '8 76?? 5 *** 2?? 83 9' ;
?? s(21):= ' 3????? 4***6????? 7 ' ;
?
?? slot_values.EXTEND(21);? ----- 對VARRAY數組(第一維)進行初始化
??
?? FOR i IN 1..21 LOOP
?????? IF p_str IS NOT NULL THEN
????????? s(i):= SUBSTR(p_str,(i-1)*21+1,21);
?????? END IF;
?
?????? slot_values(i) := t2_num();????? ----- 對VARRAY數組(第二維)進行初始化
?????? slot_values(i).EXTEND(21);
?????? FOR j IN 1..21 LOOP
?????????? slot_values(i)(j) := empty_set;?????????????? -- 為每個坐標賦予完整的候選數字清單
?????? END LOOP;
?? END LOOP;
??
?? deleted_by := slot_values;???? ---- 初始化為零
?
?? DELETE sudoku_slots;
??
?? FOR i IN 1..21 LOOP
?????? FOR j IN 1..21 LOOP
?????????? IF SUBSTR(s(i),j,1) BETWEEN '1' AND '9' THEN
????????????? k := TO_NUMBER(SUBSTR(s(i),j,1));
????????????? cleanout_value(i,j,k);
?
?????????? ELSIF SUBSTR(s(i),j,1)<>'*' THEN
?????????????
????????????? ------ 發現一個未填的空單元
????????????? INSERT INTO sudoku_slots (r,c,a,s_type,s_type2)
????????????? VALUES (i,j,(CEIL(i/3)-1)*3 + CEIL(j/3)
???????????????????? ,CASE WHEN i BETWEEN 1 AND 9 AND j BETWEEN 1 AND 9 THEN 1????? ---- 根據坐標判斷屬于哪個數獨
?????????????????????????? WHEN i BETWEEN 1 AND 9 AND j BETWEEN 13 AND 21 THEN 2
?????????????????????????? WHEN i BETWEEN 13 AND 21 AND j BETWEEN 1 AND 9 THEN 4
?????????????????????????? WHEN i BETWEEN 13 AND 21 AND j BETWEEN 13 AND 21 THEN 5
?????????????????????????? ELSE 3
????????????????????? END
???????????????????? ,CASE WHEN i BETWEEN 7 AND 15 AND j BETWEEN 7 AND 15 THEN 3??? ---- 中部（標準數獨）和其它四個重疊的部分
????????????????????? END
???????????????????? );
?
?????????? END IF;
?????? END LOOP;
?? END LOOP;
?
?? v_continue :=1;
?? WHILE v_continue = 1 LOOP
???????? ---- 對空單元進行篩選，如果只有一個候選數字則視為已知答案，從空單元清單中刪除
?
???????? v_continue := 0;
????????
???????? FOR lv_rec IN (SELECT * FROM sudoku_slots) LOOP
???????????? i:=lv_rec.r;
???????????? j:=lv_rec.c;
???????????? v_idx := slot_values(i)(j).COUNT;
?????????????? IF v_idx = 0 THEN
????????????????? RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||lv_rec.r||','||lv_rec.c);
?????????????? ELSIF v_idx = 1 THEN
????????????????? k := slot_values(i)(j).FIRST;
????????????????? cleanout_value(i,j,k);
?
????????????????? v_continue := 1;??? ---- 繼續循環，因為本次刪除可能導致產生新的已知單元格
????????????????? s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
?????????????????
????????????????? DELETE sudoku_slots WHERE r=lv_rec.r AND c=lv_rec.c; ---- 本單元格已經非空，可以刪除
?????????????? ELSE
????????????????? UPDATE sudoku_slots SET cnt = v_idx WHERE r=lv_rec.r AND c=lv_rec.c;
?????????????? END IF;
??????????????
???????? END LOOP;
?? END LOOP;
?
?? v_continue := 1;
?
?? v_idx := 0;
?
?? ---- 對空單元格進行排序。排序原則是優先取所在的行、列、區空位最少的單元
?? WHILE v_continue >0 LOOP
???????? v_continue := 0;
?
???????? FOR lv_rec IN (SELECT s.*
????????????????????????????? ,LEAST(r_cnt,c_cnt,a_cnt) AS cnt1
????????????????????????????? ,r_cnt+c_cnt+a_cnt cnt2
???????????????????????? FROM (SELECT s.*
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY r) AS r_cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY c) AS c_cnt
???????????????????????????????????? ,COUNT(*) OVER (PARTITION BY a) AS a_cnt
???????????????????????????????? FROM sudoku_slots s
??????????????????????????????? WHERE sort_order IS NULL
??????????????????????????????? ) s
??????????????????????? ORDER BY s_type,s_type2,cnt1,cnt2,cnt--,r,c
??????????????????????? )
???????? LOOP
???????????? v_idx := v_idx +1;
???????????? UPDATE sudoku_slots SET sort_order = v_idx WHERE r=lv_rec.r AND c=lv_rec.c;
???????????? v_continue := 1;
????????????
???????????? SELECT r?????? ------ 一組指針，指向本空位后續的空位，它們的取值受制于和本空格
?????????????????? ,c?????????
?????????????????? ,a?????????
?????????????????? ,cnt???????
?????????????????? ,idx???????
?????????????????? ,sort_order
?????????????????? ,s_type????
?????????????????? ,s_type2???
?????????????????? ,(CASE WHEN s_type=1 AND lv_rec.s_type=1 AND (r,c) IN ((lv_rec.r-1,lv_rec.c),(lv_rec.r+1,lv_rec.c),(lv_rec.r,lv_rec.c-1),(lv_rec.r,lv_rec.c+1))
??????????????????????????? OR s_type=5 AND lv_rec.s_type=5 AND (r,c) IN ((lv_rec.r-1,lv_rec.c),(lv_rec.r+1,lv_rec.c),(lv_rec.r,lv_rec.c-1),(lv_rec.r,lv_rec.c+1)) AND a<>lv_rec.a
???????????????????????? THEN 1
???????????????????????? ELSE 0
???????????????????? END) AS extra_rule? ---- 1(左上角)和5(右下角)需要額外的規則，清除的數字不僅僅是本身
????????????? BULK COLLECT INTO pointers(v_idx)
????????????? FROM sudoku_slots
???????????? WHERE sort_order IS NULL???? ----- sort_order為空表示后續的空位, 前面的都有值了
?????????????????? AND (s_type = lv_rec.s_type OR s_type2 = lv_rec.s_type2)
?????????????????? AND (r = lv_rec.r OR c = lv_rec.c OR a=lv_rec.a
??????????????????????? OR s_type = lv_rec.s_type AND s_type=2 AND r IN (lv_rec.r-1,lv_rec.r+1) AND c IN (lv_rec.c-1,lv_rec.c+1)?? ---- 四個對角鄰居位置
??????????????????????? OR s_type = lv_rec.s_type AND s_type=4 AND (r,c) IN ((lv_rec.r-2,lv_rec.c-1), ------ 八個馬步位置
???????????????????????????????????????????????????????????????????????????? (lv_rec.r-2,lv_rec.c+1),
???????????????????????????????????????????????????????????????????????????? (lv_rec.r+2,lv_rec.c-1),
???????????????????????????????????????????????????????????????????????????? (lv_rec.r+2,lv_rec.c+1),
???????????????????????????????????????????????????????????????????????????? (lv_rec.r-1,lv_rec.c-2),
???????????????????????????????????????????????????????????????????????????? (lv_rec.r-1,lv_rec.c+2),
???????????????????????????????????????????????????????????????????????????? (lv_rec.r+1,lv_rec.c-2),
???????????????????????????????????????????????????????????????????????????? (lv_rec.r+1,lv_rec.c+2)
??????????????????????????????????????????????????????????????????????????? )
?????????????????????? )
?????????????????? ;
?
???????????
???????????? EXIT;
???????? END LOOP;
?
?? END LOOP;
?
?? ---- 把排好序的數據載入內存數組
?? SELECT *
???? BULK COLLECT INTO empty_slots
???? FROM sudoku_slots
???? ORDER BY sort_order;
?
?? v_continue := 1;
??
?? IF empty_slots.COUNT>0 THEN
?
????? v_idx := 1;???? --- 取第一個空單元格
????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST;? ---- 取出此位置的第一個候選值
?
????? WHILE v_idx <= empty_slots.COUNT LOOP?? ---- 遍歷所有空單元格, 主循環（最為耗時）開始
??????????? IF empty_slots(v_idx).idx IS NOT NULL THEN?????
?????????????? k := empty_slots(v_idx).idx;??? ---- 因為我采用位圖的數據結構，位置即候選值。slot_values(i)(j)(k)存什么值無所謂，本例中恒為0
?????????????????
?????????????? lv_badvalue :=0;
?
?????????????? FOR v_del IN 1..pointers(v_idx).COUNT LOOP? ---- 把數字K從后續單元格的候選清單中刪除
?????????????????? i := pointers(v_idx)(v_del).r;
?????????????????? j := pointers(v_idx)(v_del).c;
?????????????????? remove_value(i,j,k,v_idx,lv_badvalue);
?????????????????? IF pointers(v_idx)(v_del).extra_rule=1 THEN
????????????????????? IF empty_slots(v_idx).s_type=1 THEN???? ---- 左上角的連續數獨，刪除額外的數（連續值）
???????????????????????? remove_value(i,j,(CASE WHEN k=1 THEN 9 ELSE k-1 END),v_idx,lv_badvalue);
???????????????????????? remove_value(i,j,(CASE WHEN k=9 THEN 1 ELSE k+1 END),v_idx,lv_badvalue);
????????????????????? ELSIF k<>1 THEN? ------ 右下角的邊界數獨，刪除額外的數（同為合/素數）
???????????????????????? IF k IN (2,3,5,7) THEN
??????????????????????????? remove_value(i,j,2,v_idx,lv_badvalue);
??????????????????????????? remove_value(i,j,3,v_idx,lv_badvalue);
??????????????????????????? remove_value(i,j,5,v_idx,lv_badvalue);
??????????????????????????? remove_value(i,j,7,v_idx,lv_badvalue);
???????????????????????? ELSE
??????????????????????????? remove_value(i,j,4,v_idx,lv_badvalue);
??????????????????????????? remove_value(i,j,6,v_idx,lv_badvalue);
??????????????????????????? remove_value(i,j,8,v_idx,lv_badvalue);
??????????????????????????? remove_value(i,j,9,v_idx,lv_badvalue);
???????????????????????? END IF;?????????????????????
????????????????????? END IF;
?????????????????? END IF;
??????????????????
?????????????????? IF lv_badvalue = 1 THEN
????????????????????? FOR i IN 1..v_del LOOP??? ---- 把前面已刪的補回去
????????????????????????? restore_deleted_value(pointers(v_idx)(i).r,pointers(v_idx)(i).c,k,v_idx,pointers(v_idx)(i).extra_rule,empty_slots(v_idx).s_type);
?
????????????????????? END LOOP;
????????????????????? EXIT;
?????????????????? END IF;
??????????????????
?????????????? END LOOP;
?
?????????????? IF lv_badvalue =0 THEN
?
????????????????? v_idx := v_idx+1;??? ---- 找到一個未用過的值，繼續下一個空單元格
?????
????????????????? IF v_idx >empty_slots.COUNT THEN????? ----- 所有空單元格都已處理完，答案找到了
???????????????????? EXIT;
????????????????? END IF;
????????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).FIRST; ---- 取出新位置的第一個候選值
?????????????? ELSE
????????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).NEXT(k);? -- 當前值證明不可用，繼續下一個值，下輪循環將找出下一可用值
?????????????? END IF;
?
??????????? ELSE??? ---- 指針到了末尾，所有值都不可用，必須退回到上一單元格
?
?????????????? v_idx := v_idx-1;???? --- 退回到上一單元格
?????????????? IF v_idx =0 THEN????? ----- 無處可退，此題沒有答案
????????????????? v_continue := 0;
????????????????? EXIT;
?????????????? END IF;
?
?????????????? ----- 回到上一單元格，當前值證明不行，必須釋放它并置為未用
?????????????? k := empty_slots(v_idx).idx;
?
?????????????? FOR v_del IN 1..pointers(v_idx).COUNT LOOP? ---- 把數字K加回候選單
??????????????????
?????????????????? restore_deleted_value(pointers(v_idx)(v_del).r,pointers(v_idx)(v_del).c,k,v_idx,pointers(v_idx)(v_del).extra_rule,empty_slots(v_idx).s_type);
?
?????????????? END LOOP;
?
?????????????? empty_slots(v_idx).idx := slot_values(empty_slots(v_idx).r)(empty_slots(v_idx).c).NEXT(k);? -- 當前值證明不可用，繼續下一個值，下輪循環將找出下一可用值
?
??????????? END IF;
????? END LOOP;
?
?? END IF;
?
?? IF v_continue = 1 THEN
?
????? FOR v_idx IN 1..empty_slots.COUNT LOOP?????????? --取出空單元格里面填好的值，拼回字符串
??????????? i := empty_slots(v_idx).r;
??????????? j := empty_slots(v_idx).c;
??????????? k := empty_slots(v_idx).idx;
??????????? s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
?
????? END LOOP;
?
????? DBMS_OUTPUT.PUT_LINE('Answer Found:');
????? FOR i IN 1..21 LOOP? ------ 輸出答案
????????? DBMS_OUTPUT.PUT_LINE(s(i));
????? END LOOP;
?? ELSE
????? DBMS_OUTPUT.PUT_LINE('No Answer Found!');
?
?? END IF;
?
END;
/
?
/*
-- 輸出答案:
582469713***254619783
964137285***679583412
731852469***318427569
173528694***425196378
496371852***796348125
258694137***831752946
825946371698542961837
649713528341967834251
317285946725183275694
******837519624******
******152436798******
******694872315******
759184263954871369524
123769485167239547618
684523719283456281793
975438126***742815936
412976538***563924187
368215947***918736245
596341872***387692451
847692351***125478369
231857694***694153872
*/
?
?
?
?
?
?