|
|
Googled sudoku forums and found this link for previous discussions
http://forum.enjoysudoku.com/sea ... 5003f014fe0d9b10791
Here just rewrite a pl/sql recursive funtion for brute force backtracking (though it is also possible to carry on str_array for forward tracking which I think performing better than backtracking). Instead focus on the sudoku problem itself, I felt recently this brute force backtracking approach might be simply applied for the 最小生成树 as discussed recently (should be similar to sql with rownum=1 for depth first). The logical flow is simply from start point and then choosing a direct connecting point in list and then next until reaching to the end point, and then going one level up to choose another point in list, etc. It is probaly simpler than the sudoku process with well defined direct connections for each point. Whenver a shorter path to the end point is found and stored in a global variable, more branches in following loopings could be quickly cut due to accumulated larger distance before reaching to the end point. In fact if one inputs a desired (unreal) very small distance value (from start to end point) at the very begining, the recursive function may stop quickly after looping through only a couple of levels because all accumulated distances will go beyond the initial setup target value before all paths can even reach to end point. So it would be critical to find an initial small path first for the brute force backtracking recursive function to perform well. Anyway the recusive function has its own ineresting part in coding in procedural languages. See if or not I can manage to write it for the shortest path problem (it would be intersting to comapre it with sql with rownum=1).
-----------------------------------------------
CREATE OR REPLACE PACKAGE pkg_sudoku
IS
TYPE cha_array_1d IS TABLE OF char(1)
INDEX BY PLS_INTEGER;
TYPE cha_array_2d IS TABLE OF cha_array_1d
INDEX BY PLS_INTEGER;
TYPE cha_array_3d IS TABLE OF cha_array_2d
INDEX BY PLS_INTEGER;
type num_array_1d is table of number
INDEX BY PLS_INTEGER ;
type num_array_2d is table of num_array_1d
INDEX BY PLS_INTEGER ;
TYPE str_array_1d IS TABLE OF varchar2(500)
INDEX BY PLS_INTEGER;
TYPE str_array_2d IS TABLE OF str_array_1d
INDEX BY PLS_INTEGER;
function sol_sudoku(p_str IN long, out_arr IN OUT nocopy num_array_1d) return number ;
END pkg_sudoku ;
/
--===============================================================================
CREATE OR REPLACE PACKAGE BODY pkg_sudoku
IS
procedure peer_map(peer_arr IN OUT nocopy num_array_2d)
as
rid1 number ;
cid1 number ;
bid1 number ;
rid2 number ;
cid2 number ;
bid2 number ;
idx number ;
begin
for pos1 in 1..81 loop
rid1 := ceil(pos1/9) ;
cid1 := mod(pos1-1,9)+1 ;
bid1 := ceil(cid1/3) + floor((rid1-1)/3)*3 ;
idx :=0 ;
for pos2 in 1..81 loop
if pos2<>pos1 then
rid2 := ceil(pos2/9) ;
cid2 := mod(pos2-1,9)+1 ;
bid2 := ceil(cid2/3) + floor((rid2-1)/3)*3 ;
if rid2=rid1 or cid2=cid1 or bid2=bid1 then
idx := idx+1 ; --upto 20 peers for each cell excluding self
peer_arr(pos1)(idx) := pos2 ;
end if ;
end if ;
end loop ;
end loop ;
end peer_map ;
-----------------------------------------------------------------------------
function update_peers(
str_arr IN OUT nocopy str_array_1d,
flag_arr IN OUT nocopy cha_array_1d,
peer_arr IN OUT nocopy num_array_2d
) return number
as
rtn number :=0 ;
peer_pos number ;
begin
for pos in 1..81 loop
if flag_arr(pos)='N' and length(str_arr(pos))=1 then
for idx in 1..20 loop
peer_pos := peer_arr(pos)(idx) ;
str_arr(peer_pos) := replace(str_arr(peer_pos), str_arr(pos), '') ;
end loop ;
flag_arr(pos) := 'Y' ;
rtn := 1 ;
end if ;
end loop ;
return rtn ;
end update_peers ;
----------------------------------------------------------------------
procedure init_str_array(
p_str IN long,
str_arr IN OUT nocopy str_array_1d,
flag_arr IN OUT nocopy cha_array_1d,
peer_arr IN OUT nocopy num_array_2d
)
as
begin
--initialize str_arr and flag_arr
for pos in 1..81 loop
flag_arr(pos) := 'N' ;
if substr(p_str, pos, 1)>0 then
str_arr(pos) := substr(p_str, pos, 1) ;
else
str_arr(pos) := '123456789' ;
end if ;
end loop ;
--update peer cells for each filled cell
loop
exit when update_peers(str_arr, flag_arr, peer_arr)=0 ;
end loop ;
end init_str_array;
-----------------------------------------------------------------------------------
function f_backtracking(
pos IN number,
num_arr IN num_array_1d,
str_arr IN OUT nocopy str_array_1d,
out_arr IN OUT nocopy num_array_1d,
peer_arr IN OUT nocopy num_array_2d
) return number
as
next_num_arr num_array_1d :=num_arr ;
next_pos number ;
peer_pos number ;
flag number ;
begin
for i in 1..length(str_arr(pos)) loop
flag :=1 ;
if length(str_arr(pos))>1 then
--backtracking peer cells
for idx in 1..20 loop
peer_pos := peer_arr(pos)(idx) ;
if peer_pos>=pos then
exit ;
else
if num_arr(peer_pos)=substr(str_arr(pos), i, 1) then
flag :=0 ;
exit ;
end if ;
end if ;
end loop ;
end if ;
if flag=1 then
next_num_arr(pos) := substr(str_arr(pos), i, 1) ;
if pos = 81 then
out_arr := next_num_arr ;
return 1 ; --found valid solution!
else
next_pos := pos+1 ;
if f_backtracking(next_pos, next_num_arr, str_arr, out_arr, peer_arr)=1 then
return 1 ;
end if ;
end if ;
end if ;
end loop;
return 0 ;
end f_backtracking ;
----------------------------------------------------------------------------------
function sol_sudoku(
p_str IN long,
out_arr IN OUT nocopy num_array_1d
) return number
AS
num_arr num_array_1d ;
str_arr str_array_1d ;
flag_arr cha_array_1d ;
peer_arr num_array_2d ;
begin
peer_map (peer_arr) ;
init_str_array(p_str, str_arr, flag_arr, peer_arr) ;
if f_backtracking(1, num_arr, str_arr, out_arr, peer_arr)=1 then
return 1 ;
end if ;
return 0 ;
end sol_sudoku ;
--------------------------------------------------------------------------
END pkg_sudoku;
/
--=====================================================================================================
--run sql file below
--@c:\sudoku\sudoku_brute_force3
--=====================================================================================================
spool c:\temp\out.txt
set serveroutput on
set lines 200
set timing on
declare
tmp_str long ;
input_str long ;
output_str long ;
output_arr pkg_sudoku.num_array_1d ;
begin
input_str := '005300000800000020070010500400005300010070006003200080060500009004000030000009700' ;
--input_str := '1.......9.5.1...3...8..34...1.5.......9..8..2....6..7.3....4..8..2.......8..7..6.' ;
--input_str := '500600003000340000000509610392000760040000050007000004005800100003270000900001005' ;
--input_str := '8 36 7 9 2 5 7 457 1 3 1 68 85 1 9 4 ' ;
--input_str := '000000003001005600090040070000009050700000008050402000080020090003500100600000000' ; --worst one!!! reverse input string and then run
input_str := replace(input_str, ' ', '0') ;
input_str := replace(input_str, '.', '0') ;
--reverse input string
/*
for i in 1..81 loop
tmp_str := substr(input_str, i, 1)||tmp_str ;
end loop ;
input_str := tmp_str ;
*/
if pkg_sudoku.sol_sudoku(input_str, output_arr)=0 then
dbms_output.put_line('no valid solution!') ;
end if ;
--display input
dbms_output.put_line(input_str) ;
--display output
for i in 1..81 loop
output_str := output_str||output_arr(i) ;
end loop ;
dbms_output.put_line(output_str) ;
end ;
/
spool off
--=======================================================================================================
|
|
楼主: cuicg
IP卡
狗仔卡
发表于 2021-7-28 21:49
显身卡
