Solve Every Sudoku without Guessing

Everything about Sudoku that doesn't fit in one of the other sections

Re: Solve Every Sudoku without Guessing

Postby jihuyao » Thu Jan 05, 2012 5:20 am

Hi Serg,

Welcome any input in SQL optimization. Can you show the benchmark by the language you use (c/c++ or java?) similar to the 1st one below (I run PL/SQL in SQLPlus). I would think major part of the time is spent in memory usage for SQL operation (dynamic memory allocation? PGA? SGA? which I have to dig deep) based on the two benchmarks below. I will compare the dynamic SQL behavior to that of the 'static' one using real tables for box1 to box9 at some time point.

I cleaned my sql file and post the code at bottom.

Jihu

Code: Select all
  1  declare
  2  start_time  timestamp ;
  3  end_time  timestamp ;
  4  Elapsed_time  varchar2(100) ;
  5  cnt   number :=0 ;
  6  begin
  7  start_time := localtimestamp ;
  8  for i in 1..1000000 loop
  9   cnt := cnt+1 ;
 10  end loop ;
 11  end_time := localtimestamp ;
 12  Elapsed_time := end_time - start_time ;
 13  Elapsed_time := substr(Elapsed_time, instr(Elapsed_time, ' ')) ;
 14  dbms_output.put_line('cnt: '||cnt) ;
 15  dbms_output.put_line('Elapsed_time: '||Elapsed_time) ;
 16* end ;
SQL> /
cnt: 1000000
Elapsed_time:  00:00:00.122000000


Code: Select all

  1  declare
  2  start_time  timestamp ;
  3  end_time  timestamp ;
  4  Elapsed_time  varchar2(100) ;
  5  cnt   number :=0 ;
  6  begin
  7  start_time := localtimestamp ;
  8  for i in (select t1.column_value a1 from TABLE(gen_numbers(1000000)) t1) loop
  9   cnt := cnt+1 ;
 10  end loop ;
 11  end_time := localtimestamp ;
 12  Elapsed_time := end_time - start_time ;
 13  Elapsed_time := substr(Elapsed_time, instr(Elapsed_time, ' ')) ;
 14  dbms_output.put_line('cnt: '||cnt) ;
 15  dbms_output.put_line('Elapsed_time: '||Elapsed_time) ;
 16* end ;
SQL> /
cnt: 1000000
Elapsed_time:  00:00:01.785000000


this is very long: Show
Code: Select all
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 long               
      INDEX BY PLS_INTEGER;

   TYPE str_array_2d IS TABLE OF str_array_1d
      INDEX BY PLS_INTEGER;

      procedure sol_sudoku(p_str IN long) ;

END pkg_sudoku;
/

------------------------------------------------------------
------------------------------------------------------------

CREATE OR REPLACE PACKAGE BODY pkg_sudoku
IS


procedure init_array(
p_str       IN    varchar2,
box_cell    IN OUT    pkg_sudoku.num_array_2d,
row_cell    IN OUT    pkg_sudoku.num_array_2d,
col_cell    IN OUT    pkg_sudoku.num_array_2d,
box_cell_grid   IN OUT   pkg_sudoku.cha_array_3d
) as

v_pos      BINARY_INTEGER ;

begin

for i in 1..9 loop

   for j in 1..9 loop

      v_pos := (i-1)*3+trunc((i-1)/3)*18+j+trunc((j-1)/3)*6 ;

      row_cell(i)(j) := substr(p_str, (i-1)*9+j, 1) ;      
      col_cell(i)(j) := substr(p_str, i+(j-1)*9, 1) ;
      box_cell(i)(j) := substr(p_str, v_pos, 1) ;

      for k in 1..9 loop

         box_cell_grid(i)(j)(k) := 'x' ;

      end loop;

   end loop ;

end loop ;

end init_array ;

-----------------------------------------------------------

procedure fill_box_cell_peer(
i1      IN    BINARY_INTEGER,
k1      IN    BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
box_cell_grid   IN OUT   nocopy   pkg_sudoku.cha_array_3d
) as

begin

for j in 1..9 loop

   if box_cell_grid(i1)(j)(k1) = 'x' then box_cell_grid(i1)(j)(k1) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

end loop ;

end fill_box_cell_peer ;

------------------------------------------------------

procedure fill_row_cell_peer(
m1      IN    BINARY_INTEGER,
k1      IN    BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
box_cell_grid   IN OUT   nocopy   pkg_sudoku.cha_array_3d
) as

i1       BINARY_INTEGER ;
j1       BINARY_INTEGER ;

begin

for n in 1..9 loop

   i1 := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
   j1 := 1+mod((m1-1),3)*3+mod((n-1),3) ;

   if box_cell_grid(i1)(j1)(k1) = 'x' then box_cell_grid(i1)(j1)(k1) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

end loop ;

end fill_row_cell_peer ;

-----------------------------------------------------------

procedure fill_col_cell_peer(
n1      IN    BINARY_INTEGER,
k1      IN    BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
box_cell_grid   IN OUT   nocopy   pkg_sudoku.cha_array_3d
) as

i1       BINARY_INTEGER ;
j1       BINARY_INTEGER ;

begin

for m in 1..9 loop

   i1 := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
   j1 := 1+mod((m-1),3)*3+mod((n1-1),3) ;

   if box_cell_grid(i1)(j1)(k1) = 'x' then box_cell_grid(i1)(j1)(k1) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

end loop ;

end fill_col_cell_peer ;

-----------------------------------------------------------

procedure fill_box_cell_grid(
i1      IN   BINARY_INTEGER,
j1      IN   BINARY_INTEGER,
k1      IN   BINARY_INTEGER,
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
box_cell_grid   IN OUT   nocopy   pkg_sudoku.cha_array_3d
) AS

m1       BINARY_INTEGER ;
n1       BINARY_INTEGER ;

begin

m1 := trunc((i1-1)/3)*3+trunc((j1-1)/3)+1 ;
n1 := (2-mod(9-i1,3))*3+3-mod(9-j1,3) ;

--if box_cell_grid(i1)(j1)(k1) = 'x' then

   box_cell_grid(i1)(j1)(k1) := '1' ; chg_x_cnt := chg_x_cnt+1 ; fil_cnt := fil_cnt+1 ;

--end if ;
               
for k in 1..9 loop
            
   if box_cell_grid(i1)(j1)(k) = 'x' then box_cell_grid(i1)(j1)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;         
         
end loop ;

fill_box_cell_peer(i1, k1, chg_x_cnt, box_cell_grid) ;
fill_row_cell_peer(m1, k1, chg_x_cnt, box_cell_grid) ;
fill_col_cell_peer(n1, k1, chg_x_cnt, box_cell_grid) ;

end fill_box_cell_grid ;         

-----------------------------------------------------------

procedure init_box_cell_grid(
fil_cnt      IN OUT   BINARY_INTEGER,
chg_x_cnt   IN OUT   BINARY_INTEGER,
box_cell_grid   IN OUT   pkg_sudoku.cha_array_3d,
box_cell   IN OUT   pkg_sudoku.num_array_2d
) AS

m       BINARY_INTEGER ;
n       BINARY_INTEGER ;
k1       BINARY_INTEGER ;

begin

for i in 1..9 loop

   for j in 1..9 loop

      if box_cell(i)(j) > 0 then

         k1 := box_cell(i)(j) ;

         fill_box_cell_grid(i, j, k1, fil_cnt, chg_x_cnt, box_cell_grid) ;

      end if ;

   end loop ;

end loop ;

end init_box_cell_grid ;         


-----------------------------------------------------------

procedure loop_naked_single_in_box(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
row_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
sudoku_str   IN OUT   nocopy   varchar2
) AS

m      BINARY_INTEGER ;
n      BINARY_INTEGER ;
k1      BINARY_INTEGER ;
k2      BINARY_INTEGER ;

v_pos      BINARY_INTEGER ;
chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

loop

chg_cnt := chg_x_cnt ;

for i in 1..9 loop

   for j in 1..9 loop   
         
      x_cnt := 0  ; x_cat := '' ;

      for k in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||k ; end if ;
      
      end loop ;

      row_x_pos(i)(j) := x_cat ;

      
      if x_cnt = 1 then    --found naked single in box   

         k1 := substr(x_cat, 1, 1) ;
         box_cell(i)(j) := k1 ;   

         v_pos := (i-1)*3+trunc((i-1)/3)*18+j+trunc((j-1)/3)*6 ;
         sudoku_str := substr(sudoku_str, 1, v_pos-1)||box_cell(i)(j)||substr(sudoku_str, v_pos+1) ;



         fill_box_cell_grid(i, j, k1, fil_cnt, chg_x_cnt, cell_grid) ;
                  
      end if ;   
      

   end loop ;

end loop ;

if chg_x_cnt = chg_cnt then exit ; end if ;

end loop ;

end loop_naked_single_in_box ;

----------------------------------------------------------------------

procedure loop_naked_pair_in_box(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
row_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

m      BINARY_INTEGER ;
n      BINARY_INTEGER ;
k1      BINARY_INTEGER ;
k2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for i in 1..9 loop

   for j in 1..9 loop   
         
      x_cnt := 0  ; x_cat := '' ;

      for k in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||k ; end if ;
      
      end loop ;

      row_x_pos(i)(j) := x_cat ;

      if x_cnt = 2 then
   
         k1 := substr(x_cat, 1, 1) ;
         k2 := substr(x_cat, 2, 1) ;

         for jj in 1..j-1 loop

            if row_x_pos(i)(j) = row_x_pos(i)(jj) then   --found naked pair in box
      
               --fill peers in box
               for jjj in 1..9 loop
                  
                  if jjj <> jj and jjj <> j then
   
                     if cell_grid(i)(jjj)(k1) = 'x' then cell_grid(i)(jjj)(k1) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i)(jjj)(k2) = 'x' then cell_grid(i)(jjj)(k2) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

                  end if ;

               end loop

               exit ;   

            end if ;

         end loop ;

      end if ;   
      

   end loop ;

end loop ;

end loop_naked_pair_in_box ;

--------------------------------------------------------------------

procedure loop_hidden_single_in_box(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
sudoku_str   IN OUT   nocopy   varchar2
) AS

j1      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

m1      BINARY_INTEGER ;
n1      BINARY_INTEGER ;

ii      BINARY_INTEGER ;
jj      BINARY_INTEGER ;

v_pos      BINARY_INTEGER ;
chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

loop

chg_cnt := chg_x_cnt ;

for i in 1..9 loop

   for k in 1..9 loop   
         
      x_cnt := 0  ; x_cat := '' ;

      for j in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||j ; end if ;
      
      end loop ;

      col_x_pos(i)(k) := x_cat ;
      
      if x_cnt = 1 then    --found hidden single in box   

         j1 := substr(x_cat, 1, 1) ;

         box_cell(i)(j1) := k ;

         v_pos := (i-1)*3+trunc((i-1)/3)*18+j1+trunc((j1-1)/3)*6 ;
         sudoku_str := substr(sudoku_str, 1, v_pos-1)||box_cell(i)(j1)||substr(sudoku_str, v_pos+1) ;

         

         fill_box_cell_grid(i, j1, k, fil_cnt, chg_x_cnt, cell_grid) ;

      end if ;         

   end loop ;

end loop ;

if chg_x_cnt = chg_cnt then exit ; end if ;

end loop ;

end loop_hidden_single_in_box ;

------------------------------------------------------------------

procedure loop_hidden_pair_in_box(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

j1      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

m1      BINARY_INTEGER ;
n1      BINARY_INTEGER ;

ii      BINARY_INTEGER ;
jj      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for i in 1..9 loop

   for k in 1..9 loop
   
         
      x_cnt := 0  ; x_cat := '' ;

      for j in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||j ; end if ;
      
      end loop ;

      col_x_pos(i)(k) := x_cat ;

      if x_cnt = 2 then   
   
         j1 := substr(x_cat, 1, 1) ;
         j2 := substr(x_cat, 2, 1) ;

         for kk in 1..k-1 loop

            if col_x_pos(i)(k) = col_x_pos(i)(kk) then   --found hidden pair in box
      
               --fill peers in box
               for kkk in 1..9 loop
                  
                  if kkk <> kk and kkk <> k then
   
                     if cell_grid(i)(j1)(kkk) = 'x' then cell_grid(i)(j1)(kkk) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i)(j2)(kkk) = 'x' then cell_grid(i)(j2)(kkk) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

                  end if ;

               end loop

               exit ;   

            end if ;

         end loop ;

      end if ;      

   end loop ;

end loop ;

end loop_hidden_pair_in_box ;

----------------------------------------------------------------------

procedure loop_pointing_pair_in_box(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

j1      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

m1      BINARY_INTEGER ;
n1      BINARY_INTEGER ;

ii      BINARY_INTEGER ;
jj      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for i in 1..9 loop

   for k in 1..9 loop
   
         
      x_cnt := 0  ; x_cat := '' ;

      for j in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||j ; end if ;
      
      end loop ;

      col_x_pos(i)(k) := x_cat ;
      
      if x_cnt = 2 then   
   
         j1 := substr(x_cat, 1, 1) ;
         j2 := substr(x_cat, 2, 1) ;
         
         if trunc((j1-1)/3) = trunc((j2-1)/3) then    --found row pointing pair in box
            
            --note m1 = m2
            m1 := trunc((i-1)/3)*3+trunc((j1-1)/3)+1 ;
            n1 := (2-mod(9-i,3))*3+3-mod(9-j1,3) ;

            --m2 := trunc((i-1)/3)*3+trunc((j2-1)/3)+1 ;
            --n2 := (2-mod(9-i,3))*3+3-mod(9-j2,3) ;

            for n in 1..9 loop

               ii := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
               jj := 1+mod((m1-1),3)*3+mod((n-1),3) ;

               if ii <> i then

                  if cell_grid(ii)(jj)(k)  = 'x' then cell_grid(ii)(jj)(k)  := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

               end if ;

            end loop ;               
         
         elsif mod(9-j1,3) = mod(9-j2,3) then       --found col pointing pair in box

            --note n1 = n2
            m1 := trunc((i-1)/3)*3+trunc((j1-1)/3)+1 ;
            n1 := (2-mod(9-i,3))*3+3-mod(9-j1,3) ;

            --m2 := trunc((i-1)/3)*3+trunc((j2-1)/3)+1 ;
            --n2 := (2-mod(9-i,3))*3+3-mod(9-j2,3) ;

            for m in 1..9 loop

               ii := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
               jj := 1+mod((m-1),3)*3+mod((n1-1),3) ;

               if ii <> i then

                  if cell_grid(ii)(jj)(k)  = 'x' then cell_grid(ii)(jj)(k)  := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

               end if ;

            end loop ;
               
         end if ;                         

      end if ;      

   end loop ;

end loop ;

end loop_pointing_pair_in_box ;

-------------------------------------------------------------------

------------------------------------------------------------------

procedure loop_pointing_triple_in_box(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

j1      BINARY_INTEGER ;
j2      BINARY_INTEGER ;
j3      BINARY_INTEGER ;

m1      BINARY_INTEGER ;
n1      BINARY_INTEGER ;

ii      BINARY_INTEGER ;
jj      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for i in 1..9 loop

   for k in 1..9 loop
   
         
      x_cnt := 0  ; x_cat := '' ;

      for j in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||j ; end if ;
      
      end loop ;

      col_x_pos(i)(k) := x_cat ;
      
      if x_cnt = 3 then   
   
         j1 := substr(x_cat, 1, 1) ;
         j2 := substr(x_cat, 2, 1) ;
         j3 := substr(x_cat, 3, 1) ;
         
         if trunc((j1-1)/3) = trunc((j2-1)/3) and trunc((j2-1)/3) = trunc((j3-1)/3) then    --found row pointing triple in box
            
            --dbms_output.put_line('found row pointing triple in box ') ;

            --note m1 = m2 and m2 = m3
            m1 := trunc((i-1)/3)*3+trunc((j1-1)/3)+1 ;
            n1 := (2-mod(9-i,3))*3+3-mod(9-j1,3) ;

            --m2 := trunc((i-1)/3)*3+trunc((j2-1)/3)+1 ;
            --n2 := (2-mod(9-i,3))*3+3-mod(9-j2,3) ;

            --m3 := trunc((i-1)/3)*3+trunc((j3-1)/3)+1 ;
            --n3 := (2-mod(9-i,3))*3+3-mod(9-j3,3) ;

            for n in 1..9 loop

               ii := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
               jj := 1+mod((m1-1),3)*3+mod((n-1),3) ;

               if ii <> i then

                  if cell_grid(ii)(jj)(k)  = 'x' then cell_grid(ii)(jj)(k)  := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

               end if ;

            end loop ;               
         
         elsif mod(9-j1,3) = mod(9-j2,3) and mod(9-j2,3) = mod(9-j3,3) then       --found col pointing triple in box

            --dbms_output.put_line('found col pointing triple in box ') ;

            --note n1 = n2 and n2 = n3
            m1 := trunc((i-1)/3)*3+trunc((j1-1)/3)+1 ;
            n1 := (2-mod(9-i,3))*3+3-mod(9-j1,3) ;

            --m2 := trunc((i-1)/3)*3+trunc((j2-1)/3)+1 ;
            --n2 := (2-mod(9-i,3))*3+3-mod(9-j2,3) ;

            --m3 := trunc((i-1)/3)*3+trunc((j3-1)/3)+1 ;
            --n3 := (2-mod(9-i,3))*3+3-mod(9-j3,3) ;

            for m in 1..9 loop

               ii := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
               jj := 1+mod((m-1),3)*3+mod((n1-1),3) ;

               if ii <> i then

                  if cell_grid(ii)(jj)(k)  = 'x' then cell_grid(ii)(jj)(k)  := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

               end if ;

            end loop ;
               
         end if ;                         

      end if ;      

   end loop ;

end loop ;

end loop_pointing_triple_in_box ;

--------------------------------------------------------------------

------------------------------------------------------------------

procedure loop_naked_pair_in_row(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
row_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

k1      BINARY_INTEGER ;
k2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for m in 1..9 loop

   for n in 1..9 loop

      i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
      j := 1+mod((m-1),3)*3+mod((n-1),3) ;   
         
      x_cnt := 0  ; x_cat := '' ;

      for k in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||k ; end if ;
      
      end loop ;

      row_x_pos(m)(n) := x_cat ;
         
      if x_cnt = 2 then
   
         k1 := substr(x_cat, 1, 1) ;
         k2 := substr(x_cat, 2, 1) ;

         for nn in 1..n-1 loop

            if row_x_pos(m)(n) = row_x_pos(m)(nn) then   --found naked pair in row cell unit

               --dbms_output.put_line('found naked pair in row cell unit!!!') ;
      
               --fill peers in row cell unit
               for nnn in 1..9 loop
                  
                  if nnn <> nn and nnn <> n then

                     i := 1+trunc((m-1)/3)*3+trunc((nnn-1)/3) ;
                     j := 1+mod((m-1),3)*3+mod((nnn-1),3) ;
   
                     if cell_grid(i)(j)(k1) = 'x' then cell_grid(i)(j)(k1) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i)(j)(k2) = 'x' then cell_grid(i)(j)(k2) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

                  end if ;

               end loop

               exit ;   

            end if ;

         end loop ;

      end if ;      

   end loop ;

end loop ;

end loop_naked_pair_in_row ;

--------------------------------------------------------------------

procedure loop_hidden_single_in_row(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
sudoku_str   IN OUT   nocopy   varchar2
) AS

n1      BINARY_INTEGER ;
n2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

v_pos      BINARY_INTEGER ;
chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

loop

chg_cnt := chg_x_cnt ;

for m in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for n in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||n ; end if ;
      
      end loop ;

      col_x_pos(m)(k) := x_cat ;
      
      if x_cnt = 1 then    --found hidden single in row cell unit   

         n1 := substr(x_cat, 1, 1) ;

         i := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n1-1),3) ;

         box_cell(i)(j) := k ;

         v_pos := (i-1)*3+trunc((i-1)/3)*18+j+trunc((j-1)/3)*6 ;
         sudoku_str := substr(sudoku_str, 1, v_pos-1)||box_cell(i)(j)||substr(sudoku_str, v_pos+1) ;

      

         fill_box_cell_grid(i, j, k, fil_cnt, chg_x_cnt, cell_grid) ;

      end if ;      

   end loop ;

end loop ;

if chg_x_cnt = chg_cnt then exit ; end if ;

end loop ;

end loop_hidden_single_in_row ;

-----------------------------------------------------------------------

procedure loop_hidden_pair_in_row(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

n1      BINARY_INTEGER ;
n2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for m in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for n in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||n ; end if ;
      
      end loop ;

      col_x_pos(m)(k) := x_cat ;

      if x_cnt = 2 then
   
         n1 := substr(x_cat, 1, 1) ;
         n2 := substr(x_cat, 2, 1) ;

         i1 := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
         j1 := 1+mod((m-1),3)*3+mod((n1-1),3) ;

         i2 := 1+trunc((m-1)/3)*3+trunc((n2-1)/3) ;
         j2 := 1+mod((m-1),3)*3+mod((n2-1),3) ;

         for kk in 1..k-1 loop

            if col_x_pos(m)(k) = col_x_pos(m)(kk) then   --found hidden pair in row cell unit
      
               --fill peers in row cell unit
               for kkk in 1..9 loop
                  
                  if kkk <> kk and kkk <> k then
   
                     if cell_grid(i1)(j1)(kkk) = 'x' then cell_grid(i1)(j1)(kkk) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i2)(j2)(kkk) = 'x' then cell_grid(i2)(j2)(kkk) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

                  end if ;

               end loop

               exit ;   

            end if ;

         end loop ;

      end if ;         

   end loop ;

end loop ;

end loop_hidden_pair_in_row ;

-----------------------------------------------------------------------------------------

procedure loop_pointing_pair_in_row(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

n1      BINARY_INTEGER ;
n2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for m in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for n in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||n ; end if ;
      
      end loop ;

      col_x_pos(m)(k) := x_cat ;

      if x_cnt = 2 then
   
         n1 := substr(x_cat, 1, 1) ;
         n2 := substr(x_cat, 2, 1) ;

         i1 := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
         j1 := 1+mod((m-1),3)*3+mod((n1-1),3) ;

         i2 := 1+trunc((m-1)/3)*3+trunc((n2-1)/3) ;
         j2 := 1+mod((m-1),3)*3+mod((n2-1),3) ;
         
         if i1 = i2 then    --found pointing pair in row cell unit (for box cell grid i1)

            --dbms_output.put_line('found pointing pair in row cell unit ') ;

            for jj in 1..9 loop

               if jj <> j1 and jj <> j2 then

                  if cell_grid(i1)(jj)(k) = 'x' then cell_grid(i1)(jj)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                  
               end if ;

            end loop ;

         end if ;

      end if ;   
      
   end loop ;

end loop ;

end loop_pointing_pair_in_row ;

---------------------------------------------------------------------
--------------------------------------------------------------------

procedure loop_pointing_triple_in_row(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

n1      BINARY_INTEGER ;
n2      BINARY_INTEGER ;
n3      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

i3      BINARY_INTEGER ;
j3      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for m in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for n in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||n ; end if ;
      
      end loop ;

      col_x_pos(m)(k) := x_cat ;

      if x_cnt = 3 then
   
         n1 := substr(x_cat, 1, 1) ;
         n2 := substr(x_cat, 2, 1) ;
         n2 := substr(x_cat, 3, 1) ;

         i1 := 1+trunc((m-1)/3)*3+trunc((n1-1)/3) ;
         j1 := 1+mod((m-1),3)*3+mod((n1-1),3) ;

         i2 := 1+trunc((m-1)/3)*3+trunc((n2-1)/3) ;
         j2 := 1+mod((m-1),3)*3+mod((n2-1),3) ;

         i3 := 1+trunc((m-1)/3)*3+trunc((n3-1)/3) ;
         j3 := 1+mod((m-1),3)*3+mod((n3-1),3) ;
         
         if i1 = i2 and i2 = i3 then    --found pointing triple in row cell unit (for box cell grid i1)

            --dbms_output.put_line('found pointing triple in row cell unit ') ;

            for jj in 1..9 loop

               if jj <> j1 and jj <> j2 and jj<> j3 then

                  if cell_grid(i1)(jj)(k) = 'x' then cell_grid(i1)(jj)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                  
               end if ;

            end loop ;

         end if ;

      end if ;   
      
   end loop ;

end loop ;

end loop_pointing_triple_in_row ;

------------------------------------------------------------
--------------------------------------------------------------------

procedure loop_naked_pair_in_col(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
row_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

k1      BINARY_INTEGER ;
k2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for n in 1..9 loop

   for m in 1..9 loop

      i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
      j := 1+mod((m-1),3)*3+mod((n-1),3) ;   
         
      x_cnt := 0  ; x_cat := '' ;

      for k in 1..9 loop
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||k ; end if ;
      
      end loop ;

      row_x_pos(n)(m) := x_cat ;

      if x_cnt = 2 then
   
         k1 := substr(x_cat, 1, 1) ;
         k2 := substr(x_cat, 2, 1) ;

         for mm in 1..m-1 loop

            if row_x_pos(n)(m) = row_x_pos(n)(mm) then   --found naked pair in col cell unit

               --dbms_output.put_line('found naked pair in col cell unit!!!') ;
      
               --fill peers in col cell unit
               for mmm in 1..9 loop
                  
                  if mmm <> mm and mmm <> m then

                     i := 1+trunc((mmm-1)/3)*3+trunc((n-1)/3) ;
                     j := 1+mod((mmm-1),3)*3+mod((n-1),3) ;
   
                     if cell_grid(i)(j)(k1) = 'x' then cell_grid(i)(j)(k1) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i)(j)(k2) = 'x' then cell_grid(i)(j)(k2) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

                  end if ;

               end loop

               exit ;   

            end if ;

         end loop ;

      end if ;   
      
   end loop ;

end loop ;

end loop_naked_pair_in_col ;

-------------------------------------------------------------------

procedure loop_hidden_single_in_col(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
sudoku_str   IN OUT   nocopy   varchar2
) AS

m1      BINARY_INTEGER ;
m2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

v_pos      BINARY_INTEGER ;
chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

loop

chg_cnt := chg_x_cnt ;

for n in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for m in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||m ; end if ;
      
      end loop ;

      col_x_pos(n)(k) := x_cat ;

      
      if x_cnt = 1 then    --found hidden single in col cell unit   

         m1 := substr(x_cat, 1, 1) ;

         i := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m1-1),3)*3+mod((n-1),3) ;

         box_cell(i)(j) := k ;

         v_pos := (i-1)*3+trunc((i-1)/3)*18+j+trunc((j-1)/3)*6 ;
         sudoku_str := substr(sudoku_str, 1, v_pos-1)||box_cell(i)(j)||substr(sudoku_str, v_pos+1) ;

         

         fill_box_cell_grid(i, j, k, fil_cnt, chg_x_cnt, cell_grid) ;

      end if ;         

   end loop ;

end loop ;

if chg_x_cnt = chg_cnt then exit ; end if ;

end loop ;

end loop_hidden_single_in_col ;

-------------------------------------------------------------------------

procedure loop_hidden_pair_in_col(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

m1      BINARY_INTEGER ;
m2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for n in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for m in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||m ; end if ;
      
      end loop ;

      col_x_pos(n)(k) := x_cat ;

      if x_cnt = 2 then
   
         m1 := substr(x_cat, 1, 1) ;
         m2 := substr(x_cat, 2, 1) ;

         i1 := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
         j1 := 1+mod((m1-1),3)*3+mod((n-1),3) ;

         i2 := 1+trunc((m2-1)/3)*3+trunc((n-1)/3) ;
         j2 := 1+mod((m2-1),3)*3+mod((n-1),3) ;

         for kk in 1..k-1 loop

            if col_x_pos(n)(k) = col_x_pos(n)(kk) then   --found hidden pair in col cell unit
      
               --fill peers in col cell unit
               for kkk in 1..9 loop
                  
                  if kkk <> kk and kkk <> k then
   
                     if cell_grid(i1)(j1)(kkk) = 'x' then cell_grid(i1)(j1)(kkk) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i2)(j2)(kkk) = 'x' then cell_grid(i2)(j2)(kkk) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;

                  end if ;

               end loop

               exit ;   

            end if ;

         end loop ;

      end if ;   
      
   end loop ;

end loop ;

end loop_hidden_pair_in_col ;

----------------------------------------------------------------------------------------------

procedure loop_pointing_pair_in_col(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

m1      BINARY_INTEGER ;
m2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for n in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for m in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||m ; end if ;
      
      end loop ;

      col_x_pos(n)(k) := x_cat ;
      
      if x_cnt = 2 then
   
         m1 := substr(x_cat, 1, 1) ;
         m2 := substr(x_cat, 2, 1) ;

         i1 := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
         j1 := 1+mod((m1-1),3)*3+mod((n-1),3) ;

         i2 := 1+trunc((m2-1)/3)*3+trunc((n-1)/3) ;
         j2 := 1+mod((m2-1),3)*3+mod((n-1),3) ;
         
         if i1 = i2 then    --found pointing pair in col cell unit (for box cell grid i1)

            --dbms_output.put_line('found pointing pair in col cell unit ') ;

            for jj in 1..9 loop

               if jj <> j1 and jj <> j2 then

                  if cell_grid(i1)(jj)(k) = 'x' then cell_grid(i1)(jj)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                  
               end if ;

            end loop ;

         end if ;

      end if ;   
      
   end loop ;

end loop ;

end loop_pointing_pair_in_col ;

----------------------------------------------------------------------
--------------------------------------------------------------------

procedure loop_pointing_triple_in_col(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

m1      BINARY_INTEGER ;
m2      BINARY_INTEGER ;
m3      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

i3      BINARY_INTEGER ;
j3      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for n in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for m in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||m ; end if ;
      
      end loop ;

      col_x_pos(n)(k) := x_cat ;
      
      if x_cnt = 3 then
   
         m1 := substr(x_cat, 1, 1) ;
         m2 := substr(x_cat, 2, 1) ;
         m3 := substr(x_cat, 3, 1) ;

         i1 := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
         j1 := 1+mod((m1-1),3)*3+mod((n-1),3) ;

         i2 := 1+trunc((m2-1)/3)*3+trunc((n-1)/3) ;
         j2 := 1+mod((m2-1),3)*3+mod((n-1),3) ;
         
         i3 := 1+trunc((m3-1)/3)*3+trunc((n-1)/3) ;
         j3 := 1+mod((m3-1),3)*3+mod((n-1),3) ;
         
         if i1 = i2 and i2 = i3 then    --found pointing triple in col cell unit (for box cell grid i1)

            --dbms_output.put_line('found pointing triple in col cell unit ') ;

            for jj in 1..9 loop

               if jj <> j1 and jj <> j2 and jj <> j3 then

                  if cell_grid(i1)(jj)(k) = 'x' then cell_grid(i1)(jj)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                  
               end if ;

            end loop ;

         end if ;

      end if ;   
      
   end loop ;

end loop ;

end loop_pointing_triple_in_col ;

--------------------------------------------------------------------
--------------------------------------------------------------------

procedure loop_x_wing_in_row(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

n1      BINARY_INTEGER ;
n2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for m in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for n in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||n ; end if ;
      
      end loop ;

      col_x_pos(m)(k) := x_cat ;

      if x_cnt = 2 then
   
         n1 := substr(x_cat, 1, 1) ;
         n2 := substr(x_cat, 2, 1) ;

         --check another row for same pattern
         for mm in 1..m-1 loop

            if col_x_pos(m)(k) = col_x_pos(mm)(k) then   --found x-wing in row cell unit (in both m and mm rows k must be in n1 or n2)
               
               --dbms_output.put_line('found x-wing in row cell unit') ;

               for mmm in 1..9 loop

                  if mmm <> m and mmm <> mm then

                     i1 := 1+trunc((mmm-1)/3)*3+trunc((n1-1)/3) ;
                     j1 := 1+mod((mmm-1),3)*3+mod((n1-1),3) ;

                     i2 := 1+trunc((mmm-1)/3)*3+trunc((n2-1)/3) ;
                     j2 := 1+mod((mmm-1),3)*3+mod((n2-1),3) ;

                     if cell_grid(i1)(j1)(k) = 'x' then cell_grid(i1)(j1)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i2)(j2)(k) = 'x' then cell_grid(i2)(j2)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                  
                  end if ;

               end loop ;

               exit ;

            end if ;

         end loop ;
                  
      end if ;   
      
   end loop ;

end loop ;

end loop_x_wing_in_row ;

--------------------------------------------------------------------

procedure loop_x_wing_in_col(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
col_x_pos   IN OUT   nocopy   pkg_sudoku.str_array_2d
) AS

m1      BINARY_INTEGER ;
m2      BINARY_INTEGER ;

i      BINARY_INTEGER ;
j      BINARY_INTEGER ;

i1      BINARY_INTEGER ;
j1      BINARY_INTEGER ;

i2      BINARY_INTEGER ;
j2      BINARY_INTEGER ;

chg_cnt      BINARY_INTEGER ;
x_cnt       BINARY_INTEGER ;
x_cat      varchar2(9) ;
   
begin

for n in 1..9 loop

   for k in 1..9 loop      
         
      x_cnt := 0  ; x_cat := '' ;

      for m in 1..9 loop

         i := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
         j := 1+mod((m-1),3)*3+mod((n-1),3) ;
 
         if cell_grid(i)(j)(k) = 'x' then x_cnt := x_cnt+1 ; x_cat := x_cat||m ; end if ;
      
      end loop ;

      col_x_pos(n)(k) := x_cat ;
      
      if x_cnt = 2 then
   
         m1 := substr(x_cat, 1, 1) ;
         m2 := substr(x_cat, 2, 1) ;

         for nn in 1..n-1 loop

            if col_x_pos(n)(k) = col_x_pos(nn)(k) then   --found x-wing in col cell unit (for both n and nn col k must in m1 and m2)
               
               --dbms_output.put_line('found x-wing in col cell unit') ;

               for nnn in 1..9 loop

                  if nnn <> n and nnn <> nn then

                     i1 := 1+trunc((m1-1)/3)*3+trunc((nnn-1)/3) ;
                     j1 := 1+mod((m1-1),3)*3+mod((nnn-1),3) ;

                     i2 := 1+trunc((m2-1)/3)*3+trunc((nnn-1)/3) ;
                     j2 := 1+mod((m2-1),3)*3+mod((nnn-1),3) ;
            
                     if cell_grid(i1)(j1)(k) = 'x' then cell_grid(i1)(j1)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
                     if cell_grid(i2)(j2)(k) = 'x' then cell_grid(i2)(j2)(k) := '0' ; chg_x_cnt := chg_x_cnt+1 ; end if ;
               
                  end if ;

               end loop ;

               exit ;

            end if ;

         end loop ;

      end if ;   
      
   end loop ;

end loop ;

end loop_x_wing_in_col ;

--------------------------------------------------------------------

----------------------------------------------------------------------

procedure loop_fill_box_cell_grid(
fil_cnt      IN OUT   nocopy   BINARY_INTEGER,
chg_x_cnt   IN OUT   nocopy   BINARY_INTEGER,
box_cell_grid    IN OUT    nocopy   pkg_sudoku.cha_array_3d,
box_cell    IN OUT    nocopy   pkg_sudoku.num_array_2d,
box_x_rowpos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
box_x_colpos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
row_x_rowpos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
row_x_colpos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
col_x_rowpos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
col_x_colpos   IN OUT   nocopy   pkg_sudoku.str_array_2d,
sudoku_str   IN OUT   nocopy   varchar2
) AS

chg_cnt1   BINARY_INTEGER ;
chg_cnt2   BINARY_INTEGER ;
chg_cnt3   BINARY_INTEGER ;

begin

loop

   loop

      loop

         chg_cnt1 := chg_x_cnt ;

         loop_naked_single_in_box( fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_rowpos, sudoku_str) ;
         loop_hidden_single_in_box(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_colpos, sudoku_str) ;
         loop_hidden_single_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_colpos, sudoku_str) ;
         loop_hidden_single_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_colpos, sudoku_str) ;
      
         if chg_x_cnt = chg_cnt1 then exit ; end if ;

      end loop ;

      if fil_cnt = 81 then exit ; end if ;

      chg_cnt2 := chg_x_cnt ;

      loop_pointing_pair_in_box(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_colpos) ;
      loop_pointing_pair_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_colpos) ;
      loop_pointing_pair_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_colpos) ;

      --loop_pointing_triple_in_box(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_colpos) ;
      --loop_pointing_triple_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_colpos) ;
      --loop_pointing_triple_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_colpos) ;


      --check x-wing
      loop_x_wing_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_colpos) ;
      loop_x_wing_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_colpos) ;


      loop_hidden_pair_in_box(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_colpos) ;
      loop_hidden_pair_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_colpos) ;
      loop_hidden_pair_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_colpos) ;

      loop_naked_pair_in_box(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_rowpos) ;
      loop_naked_pair_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_rowpos) ;
      loop_naked_pair_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_rowpos) ;

      if chg_x_cnt = chg_cnt2 then exit ; end if ;

   end loop ;

   chg_cnt3 := chg_x_cnt ;


   --loop_swordfish_in_row(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, row_x_colpos) ;
   --loop_swordfish_in_col(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, col_x_colpos) ;

   if chg_x_cnt = chg_cnt3 then exit ; end if ;

end loop ;


end loop_fill_box_cell_grid ;


---------------------------------------------------------------------------------

procedure get_box_sql(v_box OUT long)
as

v_cell_sql   long := '' ;

begin


for i in 1..9 loop

   if i < 9 then

      v_cell_sql := v_cell_sql||' select '||i||' as a from dual '||' union all ' ;
   else
      
      v_cell_sql := v_cell_sql||' select '||i||' as a from dual ' ;

   end if ;

end loop ;


--to be changed by table function for number generation
execute immediate 'create or replace view cell as '||v_cell_sql ;

v_box := 'select /*+ ordered */ * from' ;

for i in 1..9 loop

   v_box := v_box||' (select rownum as a'||i||' from dual connect by rownum < 10) c'||i||',';
   --v_box := v_box||' (select a as a'||i||' from cell) c'||i||',';

end loop ;

--dbms_output.put_line(v_box) ;


v_box := substr(v_box, 1, length(v_box)-1) ;

v_box := v_box||' where 1=1' ;

for i in 1..9 loop

   for j in 1..9 loop

      if j<>i then

         v_box := v_box||' and a'||i||'<>a'||j ;

      end if ;

   end loop ;

end loop ;


end get_box_sql ;


---------------------------------------------------------------------------------

procedure get_array_box_sql
(
box_cell_grid    IN OUT   nocopy   pkg_sudoku.cha_array_3d,
array_box_sql   OUT   nocopy   pkg_sudoku.str_array_1d
)
as

array_in         pkg_sudoku.str_array_2d ;

v_in            varchar2(100) ;
v_sql            long ;
v_box_sql         long ;

   
begin
   
v_in := '(1,2,3,4,5,6,7,8,9)' ;

get_box_sql(v_box_sql) ;

for i in 1..9 loop

   v_sql := 'select' ;

   for ii in 1..9 loop

      v_sql := v_sql||' a'||ii||' a'||i||ii||',' ;

   end loop ;

   v_sql := substr(v_sql, 1, length(v_sql)-1) ;

   v_sql := v_sql||' from ('||v_box_sql||') box where 1=1' ;

   for j in 1..9 loop

      array_in(i)(j) := v_in ;
   
      for k in 1..9 loop

         if box_cell_grid(i)(j)(k) = '0' then
            
            array_in(i)(j) := replace(array_in(i)(j), k, 0) ;

         end if ;

      end loop ;

      v_sql := v_sql||' and a'||j||' in '||array_in(i)(j) ;

   end loop ;

   array_box_sql(i) := v_sql ;

   execute immediate 'create or replace view box'||i||' as '||v_sql ;

end loop ;

end get_array_box_sql ;

---------------------------------------------------------------------------------

procedure get_grid_sql
(
box_cell_grid    IN OUT   nocopy   pkg_sudoku.cha_array_3d,
v_grid_sql   OUT      long
)
as

array_box_sql      pkg_sudoku.str_array_1d ;
array_a         pkg_sudoku.str_array_2d ;
a_str         long := '''''' ;
v_sql         long ;
v_grid         long ;

m1         number ;
n1         number ;
i1         number ;
j1         number ;
i2         number ;
j2         number ;


begin


for m in 1..9 loop

   for n in 1..9 loop

      i1 := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
      j1 := 1+mod((m-1),3)*3+mod((n-1),3) ;

      array_a(i1)(j1) := '' ;

      for nn in n+1..9 loop

         i2 := 1+trunc((m-1)/3)*3+trunc((nn-1)/3) ;
         j2 := 1+mod((m-1),3)*3+mod((nn-1),3) ;

         if i2<>i1 then array_a(i1)(j1) := array_a(i1)(j1)||' and a'||i1||j1||'<>a'||i2||j2 ; end if ;
         
      end loop ;

      for mm in m+1..9 loop

         i2 := 1+trunc((mm-1)/3)*3+trunc((n-1)/3) ;
         j2 := 1+mod((mm-1),3)*3+mod((n-1),3) ;

         if i2<>i1 then array_a(i1)(j1) := array_a(i1)(j1)||' and a'||i1||j1||'<>a'||i2||j2 ; end if ;

      end loop ;

      --dbms_output.put_line( array_a(i1)(j1) ) ;

   end loop ;

end loop ;


for m in 1..9 loop

   for n in 1..9 loop

      i1 := 1+trunc((m-1)/3)*3+trunc((n-1)/3) ;
      j1 := 1+mod((m-1),3)*3+mod((n-1),3) ;

      a_str := a_str||'||'||'a'||i1||j1 ;

   end loop ;

end loop ;


get_array_box_sql (box_cell_grid, array_box_sql) ;


v_sql := 'select /*+ ordered */ '||a_str||' as sudoku_str from' ;


for i in 1..9 loop

   v_sql := v_sql||' ('||array_box_sql(i)||') box'||i||',' ;

end loop ;

v_sql := substr(v_sql, 1, length(v_sql)-1) ;


v_sql := v_sql||' where 1=1' ;

for i in 1..9 loop

   for j in 1..9 loop

      v_sql := v_sql||array_a(i)(j) ;
      
   end loop ;

end loop ;

v_grid_sql := v_sql ;

execute immediate 'create or replace view grid as '||v_grid_sql ;

end get_grid_sql ;

---------------------------------------------------------------------------------

procedure get_sudoku_string
(box_cell_grid    IN OUT   nocopy   pkg_sudoku.cha_array_3d)
as

v_grid_sql      long ;
array_sudoku_str   pkg_sudoku.str_array_1d ;

begin

get_grid_sql(box_cell_grid, v_grid_sql) ;


--EXECUTE IMMEDIATE v_grid_sql||' and rownum=1' BULK COLLECT INTO array_sudoku_str ;
EXECUTE IMMEDIATE v_grid_sql BULK COLLECT INTO array_sudoku_str ;
dbms_output.put_line('total count='||array_sudoku_str.count) ;
dbms_output.put_line(array_sudoku_str(1)) ;


end get_sudoku_string ;

---------------------------------------------------------------------------------

procedure sol_sudoku(p_str IN long)
AS

fil_cnt      BINARY_INTEGER :=0 ;

chg_x_cnt   BINARY_INTEGER :=0 ;

box_cell_grid    pkg_sudoku.cha_array_3d ;
box_cell   pkg_sudoku.num_array_2d ;
row_cell   pkg_sudoku.num_array_2d ;
col_cell   pkg_sudoku.num_array_2d ;


box_x_rowpos   pkg_sudoku.str_array_2d;
box_x_colpos   pkg_sudoku.str_array_2d;
row_x_rowpos   pkg_sudoku.str_array_2d;
row_x_colpos   pkg_sudoku.str_array_2d;
col_x_rowpos   pkg_sudoku.str_array_2d;
col_x_colpos   pkg_sudoku.str_array_2d;


chg_cnt      BINARY_INTEGER ;
chg_cnt2   BINARY_INTEGER ;
rtn_code    number ;

sudoku_str      varchar2(81) ;


start_time      timestamp ;
end_time      timestamp ;
Elapsed_time      varchar2(100) ;


begin

dbms_output.put_line(replace(p_str, '0', '.')) ;

sudoku_str := p_str ;

init_array(p_str, box_cell, row_cell, col_cell, box_cell_grid) ;

init_box_cell_grid(fil_cnt, chg_x_cnt, box_cell_grid, box_cell) ;


dbms_output.put_line('---after initialization---') ;
dbms_output.put_line('fil_cnt='||fil_cnt) ;
dbms_output.put_line('chg_x_cnt='||chg_x_cnt) ;
dbms_output.put_line('---') ;


loop_fill_box_cell_grid(fil_cnt, chg_x_cnt, box_cell_grid, box_cell, box_x_rowpos, box_x_colpos, row_x_rowpos, row_x_colpos, col_x_rowpos, col_x_colpos, sudoku_str) ;


dbms_output.put_line('---after some simple techniques applied---') ;
dbms_output.put_line('fil_cnt='||fil_cnt) ;
dbms_output.put_line('chg_x_cnt='||chg_x_cnt) ;
dbms_output.put_line('---') ;

----------------------------------------------

start_time := localtimestamp ;
dbms_output.put_line( 'start SQL process' ) ;


get_sudoku_string(box_cell_grid) ;


dbms_output.put_line( 'end SQL process' ) ;
end_time := localtimestamp ;

Elapsed_time := end_time - start_time ;
Elapsed_time := substr(Elapsed_time, instr(Elapsed_time, ' ')) ;

dbms_output.put_line('Elapsed_time: '||Elapsed_time) ;

-----------------------------------------------


end sol_sudoku ;


END pkg_sudoku;
/

------------------------------------------------------------
------------------------------------------------------------

set linesize 300
set serveroutput on
set timing on

declare

p_str      long ;
rtn_cod      number ;

begin

--special test
--p_str := '123000000456000000789000000000123000000456000000789000000000123000000456000000789' ;

-------------------------------------------------------

--RatingProgram:gsf'ssudokuq1
--Rating:99529
--Poster:eleven
--Label:HardestSudokusThread02085;Discrepancy
p_str := '12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98' ;


--RatingProgram:NicolasJuillerat'sSudokuexplainer1.2.1
--Rating:11.9(ER/EP/ED=11.9/11.9/11.3)
--Poster:tarek
--Label:goldennugget
--p_str := '.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....' ;


--RatingProgram:gsf'ssudokuq2
--Rating:99743
--Poster:eleven
--Label:HardestSudokusThread00245;Red_Dwarf
--p_str := '12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8' ;


--RatingProgram:dukuso'ssuexrat9
--Rating:10364
--Poster:eleven
--Label:HardestSudokusThread01418;coloin
--p_str := '..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..' ;


p_str := replace(p_str, '.', '0') ;

pkg_sudoku.sol_sudoku(p_str) ;

end ;
/

--@c:\temp\pkg_sudoku_new13

jihuyao
 
Posts: 7
Joined: 21 December 2011

Re: Solve Every Sudoku without Guessing

Postby Serg » Thu Jan 05, 2012 4:43 pm

Hi, jihuyao!
jihuyao wrote:Hi Serg,

Welcome any input in SQL optimization. Can you show the benchmark by the language you use (c/c++ or java?) similar to the 1st one below (I run PL/SQL in SQLPlus).

Code: Select all
  1  declare
  2  start_time  timestamp ;
  3  end_time  timestamp ;
  4  Elapsed_time  varchar2(100) ;
  5  cnt   number :=0 ;
  6  begin
  7  start_time := localtimestamp ;
  8  for i in 1..1000000 loop
  9   cnt := cnt+1 ;
 10  end loop ;
 11  end_time := localtimestamp ;
 12  Elapsed_time := end_time - start_time ;
 13  Elapsed_time := substr(Elapsed_time, instr(Elapsed_time, ' ')) ;
 14  dbms_output.put_line('cnt: '||cnt) ;
 15  dbms_output.put_line('Elapsed_time: '||Elapsed_time) ;
 16* end ;
SQL> /
cnt: 1000000
Elapsed_time:  00:00:00.122000000

I use ordinary C language (DJGPP C free compiler) on my home notebook (Intel Core 2 Duo CPU, 2.00 GHz, 2 GB SDRAM, MS Windows XP).
I have no Oracle Database on my notebook, so I constructed benchmark very similar to your 1st example.
Code: Select all
#include <stdio.h>
#include <time.h>

main()
{
    int i, cnt;
    time_t  tbeg, tend;

    printf("Benchmark for DJGPP C language (gcc)\n\n");

    tbeg = time(NULL);

    for (i = 0; i < 1000000000; i++) {
        cnt++;
    }
    tend = time(NULL);
    printf("cnt: %1d  Execution time: %1.0f seconds\n", cnt, difftime(tend,tbeg));
}

I can measure execution time in seconds only, so I had to increase loop count to 1,000,000,000.
This is benchmark's output:
Code: Select all
Benchmark for DJGPP C language (gcc)

cnt: 1000000000  Execution time: 3 seconds

Your benchmark loops 1,000,000 times during 0.122 sec, my benchmark loops 1,000,000,000 times during 3 sec or 1,000,000 times during 0.003 sec. This is 40 times faster than PL/SQL benchmark shows.

jihuyao wrote:I would think major part of the time is spent in memory usage for SQL operation (dynamic memory allocation? PGA? SGA? which I have to dig deep) based on the two benchmarks below. I will compare the dynamic SQL behavior to that of the 'static' one using real tables for box1 to box9 at some time point.

My SQL optimization experience tells me that the most efficient way of doing smth by SQL is to choose optimal execution plan and direct SQL optimizer to follow this plan by hints. So, you need have low-level understanding - how SQL is executed to have chance to improve it.
jihuyao wrote:I cleaned my sql file and post the code at bottom.

Thank you. It is interesting for me. But your code is so huge! It contains 2229 lines. My backtracing solver is less (823 lines), provided it is not pure backtracking solver - it finds naked and hidden singles during candidate trial. I am sure pure backtracking solver would be much smaller.
So, I cannot really help you.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Solve Every Sudoku without Guessing

Postby jihuyao » Fri Jan 06, 2012 4:49 pm

Hi Serg,

Thanks for the benchmark. Rerun with loop to 1000*1000*1000 on my laptop shown below Which mainly tells the difference between c and pl/sql (and no surprise to me).

Code: Select all
  1  declare
  2  start_time  timestamp ;
  3  end_time  timestamp ;
  4  Elapsed_time  varchar2(100) ;
  5  TYPE NUM_ARR_1D IS TABLE OF NUMBER ;
  6  v_arr_num  NUM_ARR_1D := NUM_ARR_1D() ;
  7  cnt   number :=0 ;
  8  begin
  9  start_time := localtimestamp ;
 10  for i in 1..1000*1000*1000 loop
 11   cnt := cnt+1 ;
 12   --v_arr_num.extend ;
 13   --v_arr_num(i) := i ;
 14  end loop ;
 15  end_time := localtimestamp ;
 16  Elapsed_time := end_time - start_time ;
 17  Elapsed_time := substr(Elapsed_time, instr(Elapsed_time, ' ')) ;
 18  dbms_output.put_line('cnt: '||cnt) ;
 19  dbms_output.put_line('Elapsed_time: '||Elapsed_time) ;
 20* end ;
 21  /
cnt: 1000000000
Elapsed_time:  00:01:19.525000000


As to those procedures in the package, most of them can be consolidated to remove the overhead but I simply run it as analyzer (part of fun in doing sudoku).

Both normal trace and autotrace show the execution plan in which all joins use nest loop (it is understandable because hash join is not option due to none-equality and merge join is not necessary better in this case). I just ignored it because it is too long and messy to post. The underhood memory usage for sql (not pl/sql) process is my interest (although it is probably out of control) and I may go to the Oracle forum for some light (I could basically miss the fundamentals because I am not computer major).

I do code the nested trail and error only for candidate elimination but it is so painful with hard puzzles (without any hint where to start). Brute-force backtracking may be worth a try in pl/sql (compared to sql). I was just scared on its sort-of-predictable performance in pl/sql (but it may not be too bad at the end based on the benchmark.

Anyway a good journey and lots of fun.

Lastly, I tested a few varying cases with the puzzle 1 by fixing box1 and box5 and switching two digits in box9 and they have the same total count (wondering about other possible switches, humm...........).

Code: Select all
123000000
456000000
789000000
000123000
000456000
000789000
000000132
000000456
000000789

123000000456000000789000000000123000000456000000789000000000132000000456000000789

cnt=271012


123000000
456000000
789000000
000123000
000456000
000789000
000000213
000000456
000000789

123000000456000000789000000000123000000456000000789000000000213000000456000000789

cnt=271012

123000000
456000000
789000000
000123000
000456000
000789000
000000129
000000456
000000783


123000000456000000789000000000123000000456000000789000000000129000000456000000783

cnt=271012


Have a good one.

Jihu
jihuyao
 
Posts: 7
Joined: 21 December 2011

Re: Solve Every Sudoku without Guessing

Postby Serg » Tue Jan 10, 2012 5:23 pm

Hi, Jihu!
jihuyao wrote:I do code the nested trail and error only for candidate elimination but it is so painful with hard puzzles (without any hint where to start). Brute-force backtracking may be worth a try in pl/sql (compared to sql). I was just scared on its sort-of-predictable performance in pl/sql (but it may not be too bad at the end based on the benchmark.

I think is not so much sense in trying to code backtracking sudoku solving algorithms in SQL or PL/SQL. Not only because of poor performance of PL/SQL. (PL/SQL is compiled to a sort of pseudo-code (pi-code, I am not mistaken), which is then executed by PL/SQL engine - somewhat like java compiling and execiting with its performance problems.) If you use database, you should use algorithms being well suited for it. Databases can perfectly search for information. So, to use it effectively you should load to it huge amount of precalculated useful information concerning possible sudoku solutions and find solutions by appropriate query to this information.

Let's consider an example (the method described does't really work, but it is useful for describing my advice). We create a table having 81 columns (of "char" datatype) and load all possible solution grids into this table. Then we find solutions of given puzzle by a query with WHERE clause, pointing to all known digits (clues). This algorithm is not feasible because of huge amount of data to load (6*10^21 table rows). But maybe other predefined data can be used - filled boxes, filled bands/stacks or templates (see links published in new thread "New Solving Technique (I think)" on this site: http://forum.enjoysudoku.com/new-solving-technique-i-think-t30444.html).

Another my consideration: I think solving methods involving databases are more suitable for exhausive search (solving a family of puzzles) than for solving single puzzles, because it seems to consume comparable time in both cases.

It seems to me you should open new thread specially devoted to database techniques usage in solving sudoku (if you really have an interest in this area), because the theme we are considering now is rather far from this thread title ("Solve Every Sudoku without Guessing").

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Previous

Return to General