Decode360's Blog

业精于勤而荒于嬉 QQ:150355677 MSN:decode360@hotmail.com

  BlogJava :: 首页 :: 新随笔 :: 联系 ::  :: 管理 ::
  397 随笔 :: 33 文章 :: 29 评论 :: 0 Trackbacks
PLSQL解sudoku的方法
 
    2008年最后一篇,自然要来一点重量级内容,这篇摘录了论坛里newkid大牛写的解sudoku的PLSQL程序,特别值得推荐的就是分三种思想分别求解,以及PLSQL里数组的应用,基本上在平常的工作中很难用到,所以很有学习的价值。原文的地址如下:
   
    http://www.itpub.net/viewthread.php?tid=1074409&extra=page%3D1%26amp%3Bfilter%3Ddigest
 

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)
      );
 
---- 从这里下载的160个题目: http://www.sudokufans.org.cn/shudo/download/160hard.rar
 
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
*/
 
 
 
 
 
 
posted on 2008-12-31 23:13 decode360 阅读(184) 评论(0)  编辑  收藏 所属分类: 06.PLSQL

只有注册用户登录后才能发表评论。


网站导航: