|
|
参考lastwinner思路写了一个版本。
我以前的数据结构是“某个空格有哪些可能值”，现在则是“某个值可能出现在哪些位置”，这是为了方便实现lastwinner 的第四步推理。
当所有消除法都运行完毕，仍然可能有空格，这时候就得用回溯法了，这一步还没有实现。
比如下面这个题目就求不出解：
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 ' ;
lastwinner说这个方法求不出多个解的题目，但上述题目明明只有唯一解，我用其他方法验证过了。如果野花兄的程序能解出来请赐教。
CREATE OR REPLACE PROCEDURE sudoku_lw(p_str IN VARCHAR2 DEFAULT NULL)
AS
TYPE t_num IS TABLE OF NUMBER; ---- 三维数组
TYPE t2_num IS TABLE OF t_num;
TYPE t3_num IS TABLE OF t2_num;
TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
s t_str; ---- 字符串数组，存放题目
v_continue NUMBER;
e t_num := t_num(1,2,3,4,5,6,7,8,9); ---- 初始化数组
e2 t2_num := t2_num(e,e,e,e,e,e,e,e,e); ---- 初始化数组, 第二维
r t3_num := t3_num(e2,e2,e2,e2,e2,e2,e2,e2,e2); ----- 如果r(i)(j)(k)有数据，则表示数字i可能出现在第j行第k列
c t3_num := r; ----- 如果c(i)(j)(k)有数据，则表示数字i可能出现在第k行第j列
a t3_num := r; ----- 如果a(i)(j)(k)有数据，则表示数字i可能出现在第k区第k列个位置
----- 从左到右、从上到下编为9个区，每个区里面又按同样顺序编1-9号
get_a t2_num := e2; ------ 存放行列坐标和区号的换算，第i行第j列对应的区号是 get_a(i)(j)
get_a_num t2_num := e2; ------ 存放行列坐标和区内位置号的换算，第i行第j列对应的区内位置编号是 get_a_num(i)(j)
PROCEDURE known ( ----- 已知值p_val出现在p_row行和p_col列，把它从行、列、区的候选值清单中删除。
p_row IN NUMBER
,p_col IN NUMBER
,p_val IN NUMBER
)
AS
BEGIN
r(p_val)(p_row).DELETE; ----- 本行已经不可能出现p_val了
c(p_val)(p_col).DELETE; ----- 本列已经不可能出现p_val了
a(p_val)(get_a(p_row)(p_col)).DELETE; ----- 本区已经不可能出现p_val了
FOR i IN 1..9 LOOP
r(i)(p_row).DELETE(p_col); ----- 所有其他候选值都不会出现在p_row,p_col 这个坐标了
c(i)(p_col).DELETE(p_row);
a(i)(get_a(p_row)(p_col)).DELETE(get_a_num(p_row)(p_col));
r(p_val)(i).DELETE(p_col); ------ p_val不会出现在同一列的其他行了
c(p_val)(i).DELETE(p_row); ------ p_val不会出现在同一行的其他列了
FOR j IN 1..9 LOOP ------ 所有区中只要行，列和本坐标有交叉，也就不会出现p_val了
a(p_val)(get_a(p_row)(j)).DELETE(get_a_num(p_row)(j));
a(p_val)(get_a(j)(p_col)).DELETE(get_a_num(j)(p_col));
END LOOP;
END LOOP;
s(p_row) := SUBSTR(s(p_row),1,p_col-1)||p_val||SUBSTR(s(p_row),p_col+1); ---- 把已知值拼到方阵中
END known;
BEGIN
--- 测试用例
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';
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;
FOR j IN 1..9 LOOP
get_a(i)(j) := (CEIL(i/3)-1)*3+CEIL(j/3); ----- 预先算好行列坐标和区以及区内编号的对应关系并保存到数组中
get_a_num(i)(j) := (MOD(i-1,3)+1 -1 )*3 + MOD(j-1,3)+1;
IF SUBSTR(s(i),j,1) BETWEEN '1' AND '9' THEN
known(i,j,SUBSTR(s(i),j,1));
END IF;
END LOOP;
END LOOP;
v_continue := 1;
WHILE v_continue=1 LOOP
v_continue := 0;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
IF r(i)(j).COUNT=1 THEN ------- lastwinner 的第四步推理
v_continue := 1;
known(j,r(i)(j)(r(i)(j).FIRST),i);
END IF;
IF c(i)(j).COUNT=1 THEN
v_continue := 1;
known(c(i)(j)(c(i)(j).FIRST),j,i);
END IF;
IF a(i)(j).COUNT=1 THEN
v_continue := 1;
known(get_a(j)(a(i)(j).FIRST),get_a_num(j)(a(i)(j).FIRST),i);
END IF;
END LOOP;
END LOOP;
END LOOP;
DBMS_OUTPUT.PUT_LINE('result:');
FOR i IN 1..9 LOOP ------ 输出答案
DBMS_OUTPUT.PUT_LINE('~'||s(i));
END LOOP;
END sudoku_lw;
/
|
|
楼主: newkid
IP卡
狗仔卡
楼主
显身卡
发表于 2010-3-20 02:13
发表于 2010-3-21 22:10
