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
*/