|
|
在消除法的基础上加入回溯的功能，代码一下子膨胀了很多，因为要保存、恢复被删除的数据。
我的尝试方法是：找出第一个未确定位置的值，逐个位置尝试。因为这个顺序的关系，如果一个小值的正确位置是在右下方，则前面必然有很多失败的尝试。不知道有什么优化的办法没有。
CREATE OR REPLACE PROCEDURE sudoku_lw3(p_str IN VARCHAR2 DEFAULT NULL)
AS
TYPE t_num IS TABLE OF NUMBER;
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(100) INDEX BY BINARY_INTEGER;
s t_str; ---- 字符串数组，存放题目
e t_num := t_num(1,2,3,4,5,6,7,8,9);
c t2_num; ---------- 如果c(ij)(k)有数据，则表示数字i可能出现在第j行第k列
----- 如果下标为三位数，c(i0j)(k)有数据，则表示数字i可能出现在第k行第j列
----- 如果下标为四位数，c(i00j)(k)有数据，则表示数字i可能出现在第k区第k列个位置
----- 从左到右、从上到下编为9个区，每个区里面又按同样顺序编1-9号
bak t3_num; ----- 存放被删除的c()()值。第三维是个堆栈
get_a t2_num ; ------ 存放行列坐标和区号的换算，第i行第j列对应的区号是 get_a(i)(j)
get_a_num t2_num ; ------ 存放行列坐标和区内位置号的换算，第i行第j列对应的区内位置编号是 get_a_num(i)(j)
lv_ptr NUMBER;
lv_bak_ptr NUMBER;
gv_bad_answer BOOLEAN;
PROCEDURE save_bak(i NUMBER, p_deleted_by NUMBER) ---- 用消除法删去一个值之前把数据备份
AS
BEGIN
IF p_deleted_by>0 AND c.EXISTS(i) AND NOT (bak.EXISTS(p_deleted_by) AND bak(p_deleted_by).EXISTS(i)) THEN
bak(p_deleted_by)(i) := c(i);
END IF;
END save_bak;
PROCEDURE del_num (i NUMBER, j NUMBER, p_deleted_by NUMBER DEFAULT NULL)
--- 删去c(i)第j个元素, 如果p_deleted_by>0表示正在尝试，需要把删除之前的数据保存备份
AS
BEGIN
IF NOT c.EXISTS(i) OR gv_bad_answer THEN
RETURN;
END IF;
IF j IS NULL THEN
save_bak(i,p_deleted_by);
c.DELETE(i);
ELSE
save_bak(i,p_deleted_by);
c(i).DELETE(j);
IF c(i).COUNT=0 THEN ----- 全部删光了，说明这个尝试是失败的
gv_bad_answer := TRUE;
END IF;
END IF;
END del_num;
PROCEDURE known ( ----- 消除法，已知值p_val出现在p_row行和p_col列，把它从行、列、区的候选值清单中删除。
p_row IN NUMBER
,p_col IN NUMBER
,p_val IN NUMBER
,p_deleted_by IN NUMBER DEFAULT NULL
)
AS
BEGIN
del_num(p_val*10+p_row ,NULL,p_deleted_by); ----- 本行已经不可能出现p_val了
del_num(p_val*100+p_col ,NULL,p_deleted_by); ----- 本列已经不可能出现p_val了
del_num(p_val*1000+get_a(p_row)(p_col),NULL,p_deleted_by); ----- 本区已经不可能出现p_val了
IF gv_bad_answer THEN
RETURN;
END IF;
FOR i IN 1..9 LOOP
del_num(i*10+p_row,p_col ,p_deleted_by); ----- 所有其他候选值都不会出现在p_row,p_col 这个坐标了
del_num(i*100+p_col,p_row,p_deleted_by);
del_num(i*1000+get_a(p_row)(p_col),get_a_num(p_row)(p_col),p_deleted_by);
del_num(p_val*10+i,p_col,p_deleted_by); ------ p_val不会出现在同一列的其他行了
del_num(p_val*100+i,p_row,p_deleted_by); ------ p_val不会出现在同一行的其他列了
FOR j IN 1..9 LOOP ------ 所有区中只要行，列和本坐标有交叉，也就不会出现p_val了
del_num(p_val*1000+get_a(p_row)(j),get_a_num(p_row)(j),p_deleted_by);
del_num(p_val*1000+get_a(j)(p_col),get_a_num(j)(p_col),p_deleted_by);
END LOOP;
IF gv_bad_answer THEN
RETURN;
END IF;
END LOOP;
s(p_row) := SUBSTR(s(p_row),1,p_col-1)||p_val||SUBSTR(s(p_row),p_col+1); ---- 把已知值拼到方阵中
END known;
PROCEDURE del_known ( ------ 从c(p_ptr)里面取出第一个未删的位置，假设这是一个正确的位置，用消除法推理删除其他的
p_ptr IN NUMBER
,p_deleted_by IN NUMBER
)
AS
lv_row NUMBER;
lv_col NUMBER;
lv_val NUMBER := SUBSTR(p_ptr,1,1);
lv_deleted_by NUMBER := p_deleted_by;
BEGIN
CASE
WHEN p_ptr>1000 THEN
lv_row := get_a(SUBSTR(p_ptr,4))(c(p_ptr).FIRST);
lv_col := get_a_num(SUBSTR(p_ptr,4))(c(p_ptr).FIRST);
WHEN p_ptr>100 THEN
lv_row := c(p_ptr)(c(p_ptr).FIRST);
lv_col := SUBSTR(p_ptr,3);
ELSE
lv_row := SUBSTR(p_ptr,2);
lv_col := c(p_ptr)(c(p_ptr).FIRST);
END CASE;
IF p_deleted_by=-1 THEN ----- p_deleted_by=-1表示这是新一轮消除的尝试
lv_deleted_by := bak.COUNT+1; --- 获取一个新堆栈位置来存放被删除的数据
---- 当前尝试值保存到当前栈顶
save_bak(lv_val*10+lv_row,bak.COUNT);
save_bak(lv_val*100+lv_col,bak.COUNT);
save_bak(lv_val*1000+get_a(lv_row)(lv_col),bak.COUNT);
---- 在尝试当前值之前把它们删掉。如果中间失败，回溯并恢复出来的数组将不再包含这个当前值，将会从下一个开始
---- 如果从当前值以后的猜测值全部失败，则回溯到刚才保存在栈顶的状态
IF c.EXISTS(lv_val*10+lv_row) THEN
c(lv_val*10+lv_row).DELETE(lv_col);
END IF;
IF c.EXISTS(lv_val*100+lv_col) THEN
c(lv_val*100+lv_col).DELETE(lv_row);
END IF;
IF c.EXISTS(lv_val*1000+get_a(lv_row)(lv_col)) THEN
c(lv_val*1000+get_a(lv_row)(lv_col)).DELETE(get_a_num(lv_row)(lv_col));
END IF;
END IF;
known(lv_row,lv_col,lv_val,lv_deleted_by); ---- 运用消除法
RETURN;
END del_known;
PROCEDURE check_known(p_deleted_by IN NUMBER DEFAULT NULL) ---- 试图用推理的办法找出所有已知数字
AS
v_continue NUMBER := 1;
lv_ptr NUMBER;
BEGIN
WHILE v_continue=1 AND NOT gv_bad_answer LOOP
v_continue := 0;
lv_ptr := c.FIRST;
WHILE lv_ptr>0 AND NOT gv_bad_answer LOOP
IF c(lv_ptr).COUNT=1 THEN ------- lastwinner 的第四步推理: 只剩下一个位置可选，则该位置可确定
v_continue := 1;
del_known(lv_ptr,p_deleted_by);
END IF;
lv_ptr := c.NEXT(lv_ptr);
END LOOP;
END LOOP;
END check_known;
BEGIN
gv_bad_answer := FALSE;
--- 测试例子
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
get_a(i) := e; ----- 初始化，真正的值在下面计算
get_a_num(i) := e;
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;
c(i*10+j) := e;
c(i*100+j) := e;
c(i*1000+j) := e;
END LOOP;
END LOOP;
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
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;
check_known; ---- 所有已知值消除完毕，试图推理
IF NOT gv_bad_answer THEN
WHILE c.COUNT>0 LOOP --------- 还有未知值
lv_ptr := c.FIRST;
IF c(lv_ptr).COUNT>0 THEN
del_known(lv_ptr,-1); ---- 取出第一个未知值来尝试
check_known(bak.COUNT);
ELSE
gv_bad_answer := TRUE;
END IF;
IF gv_bad_answer THEN ------ 测试失败，从bak()中恢复
lv_bak_ptr := bak.COUNT; ---- 出栈
IF lv_bak_ptr>0 THEN
lv_ptr := bak(lv_bak_ptr).FIRST;
WHILE lv_ptr>0 LOOP
c(lv_ptr) := bak(lv_bak_ptr)(lv_ptr); --- 从bak()中恢复到c()
lv_ptr := bak(lv_bak_ptr).NEXT(lv_ptr);
END LOOP;
bak.DELETE(lv_bak_ptr); ---- 恢复完毕，栈顶削掉，继续下一轮尝试
gv_bad_answer := FALSE;
ELSE
EXIT;
END IF;
END IF;
END LOOP;
END IF;
IF gv_bad_answer THEN
RAISE_APPLICATION_ERROR(-20001,'no answer found');
ELSE
DBMS_OUTPUT.PUT_LINE('Answer Found:');
FOR i IN 1..9 LOOP ------ 输出答案
DBMS_OUTPUT.PUT_LINE(s(i));
END LOOP;
END IF;
END sudoku_lw3;
/
|
|
楼主: newkid
IP卡
狗仔卡
发表于 2010-4-3 22:43
显身卡
楼主
发表于 2010-4-12 13:27
