The New Sudoku Players' Forum

[sdk_fan]

[

Just to clarify, by "Descartes product", do you mean "Cartesian product" ("produit cartésien" in French ) ?

You are right, that should be Cartesian product. So what I am achieving is to save actual Cartisian products and only keep the necessary information to compute them.

[sdk_fan]

Can you tell me, whats the difference to lerxst's aproach ?

Hi, eleven, I almost missed your response.

I read lerxst's approach when dobrichev gave the link of lerxst's blog in the other forum. And I wrote lerxst for a little individual discussion. Here is my understanding of it. Lerxst, Please correct me if I am mistaken.

In his blog, Lerxst's approach is very straightforward, to join 9 row-tables. The joins are non-equi joins, meaning there is additional need and mechanism to specify the inequality constraints such like r2.c1 != r1.c1 and r2.c1 !=r1.c2, etc. Such constraints comes from the very basic Sudoku rule. Lerxst's current improvement is that he includes columns, so he need 18 tables now. (But, lerxst finds it is not helpful to include 3X3 blocks.) I am not sure if he treat these 18 tables equally, but I guess, the backbone of the approach is based on non-equi joins (as well as equi-joins since he added the 9 column tables).

The difference sounds quite trivial in some sense. My approach, if understood as joins of 27 tables, is made of natural joins ( i-e, equi-joins) only. There is no non-equi joins, so you do not need to explicitly specify Sudoku rule, which are already re-enforced at the time the 27 tables are built.

I regard Lerxst's approach (particularly his original 9 row-table version) as the mid-way between a cell-based non-equi joins and the unit(or group) based natural joins. A cell-based join approach, ("Sudoku Solver in SQL" Taro YABUKI and Hiroshi SAKUTA, a artical in Japanese with english abstract), having to specify inequality constraints like A!=B, appears to me very much a database equivalent of traditional cell-based searching approach. While the non-equi join's driving force to solve a Sudoku is the direct application of the basic Sudoku rule, the driving force of the unit-based natural join is the formation of "cogwheel circles", which I (partially) find more generic, and which I use to direct the ordering heuristic.

Nevertheless, I suspect, apart from the ordering of joins, lerxst's and my approaches will in general degrade performance on puzzles with fewer givens. However, I "slyly" avoid this degradation problem by including preprocessing based on other simpler logic. Since I think equality are stronger constraints than inequlality, I "regard" my appraoch as logic approach, therefore, I, without hesitation, include logic preprocessing before the main method is used. The preprocessing includes: subsets, and swordfish typed logic. With these, most 17s are solved or at least are degraded, so my "natural join" algorithm never has problems with them. As for those truly logically hard puzzles, the preprocessing never helps, so the natural join is the only solving mechanism.

Just out of curiosity, I turned off preprocessing and use the natural join directly on some 17 givens, I find
1. it is much slower; and some puzzles are thought harder than those truly hard ones
2. But the majority are OK puzzles, considered less harder than those logically hard puzzles.

[eleven]

Thanks for the explanations. Its about what i expcted, but i was not sure.
What i wonder is that Lerxst's dumb (as he calls it) method can be that (relatively) fast. It seems that i underestimated the database optimization.

[jihuyao]

In my opinion, SQL is a natural approach particularly to hard Sudoku and it is simple.

Based on the basic rules for 9x9 Sudoku, without filling any of the 81 cells, each cell c(i) has the same condition set and 20 constraints, that is, its value a(i) is in (1,2,3,4,5,6,7,8,9) and a(i)<>a(j) where j represents the peer cells in box, row, and column. So the following SQL statement will return all the solutions for 9x9 Sudoku (assuming unlimited database resource),

Code: Select all

select a1, …… , a81                                   --return all Sudoku solutions
from c1, …… , c81                                     --join all 81 cell tables
where a(i) in (1,2,3,4,5,6,7,8,9) and …               --same initial condition set for each cell
and a(i)<>a(j) and …                                  --same constraints for each cell and its peer cells


Given a valid puzzle, its initial setting will set different condition set for each cell (and applying any logic will further change each condition set but all the constraints remain the same), for example, the cell c(i) may only have its value a(i) in (1,2,3,4,5) after initialization and logical derivation. So the following SQL statement will return only one solution for the given valid puzzle,

Code: Select all

select a1, …… , a81                                  --return only one solution for a valid puzzle
from c1, …… , c81                                    --join all 81 cell tables
where a(i) in (1,2,3,4,5) and …                      --different initial condition set for each cell
and a(i)<>a(j) and …                                 --same constraints for each cell and its peer cells


Yes, for any puzzle, the where clause is very long, with 81 varying initial condition sets and all the constraints. However, here comes dynamic SQL to rescue, which means, constructing the SQL statement in a string and execute it dynamically.

Is SQL doing trial and error? Yes, it evaluates all possible combinations with all candidates in each cell and eliminates the invalid ones by the constraints. But indeed SQL does it efficiently in ‘SQL’ way.

[Serg]

Hi, jihuyao!
Your idea about solving puzzles by appropriate SQL query sounds interesting. It is transparent and rather simple for coding, but, but, but...
This method must compete with traditional backtracking solvers. To my experience, such solvers usually can solve 5000-10000 puzzles per second. I doubt that such query can be executed in 100 microseconds. It will require terabytes of memory to do such join, I think. I've never seen join of 81 tables. (I've seen no more than 10 tables joins.)

In any way, I am interesting in seeing your result. I think such experiment will be interesting for many people. Try your idea.

Happy New Year!
Serg

[jihuyao]

Here are three test results from running an Oracle 11g R2 database on my laptop,

1. a puzzle returning multiple solutions (grid is a database view created at run time which needs not physical storage)

Code: Select all

SQL> @c:\temp\pkg_sudoku_new11

Package created.


Package body created.

123......456......789.........123......456......789.........123......456......789
---after initialization---
fil_cnt=27
chg_x_cnt=513
---
---after some simple techniques applied---
fil_cnt=27
chg_x_cnt=513
---
start time for SQL process
end time for SQL process
Elapsed_time:  00:00:00.417000000
---
---

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.48
SQL>
SQL> select count(*) from grid ;

  COUNT(*)
----------
    283576

Elapsed: 00:12:08.27
SQL>


2. one of the hardest puzzle returns only one solution (after checking all possible combinations)

--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..' ;

Code: Select all

SQL> @c:\temp\pkg_sudoku_new11

Package created.

Elapsed: 00:00:00.05

Package body created.

Elapsed: 00:00:02.86
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..
---after initialization---
fil_cnt=22
chg_x_cnt=461
---
---after some simple techniques applied---
fil_cnt=22
chg_x_cnt=465
---
start time for SQL process
123456789457189236968327154249561873576938412831742695314275968695814327782693541
end time for SQL process
Elapsed_time:  00:01:19.281000000
---
---

PL/SQL procedure successfully completed.

Elapsed: 00:01:19.41
SQL>


3. The same puzzle as 2 but only returns the first solution (stop when it is found)

--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..' ;

Code: Select all

SQL> @c:\temp\pkg_sudoku_new11

Package created.

Elapsed: 00:00:00.04

Package body created.

Elapsed: 00:00:02.45
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..
---after initialization---
fil_cnt=22
chg_x_cnt=461
---
---after some simple techniques applied---
fil_cnt=22
chg_x_cnt=465
---
start time for SQL process
123456789457189236968327154249561873576938412831742695314275968695814327782693541
end time for SQL process
Elapsed_time:  00:00:01.034000000
---
---

PL/SQL procedure successfully completed.

Elapsed: 00:00:01.13
SQL>


It can not run much faster (on my laptop) based on the timing check below,
Possible to find better join order? yes.
Possible to remove the overhead constraints in the where clause of SQL statement? yes

Code: Select all

SQL> select count(*) from box1 ;

  COUNT(*)
----------
        96

Elapsed: 00:00:00.06
SQL> select count(*) from box2 ;

  COUNT(*)
----------
       588

Elapsed: 00:00:00.10
SQL> select count(*) from box3 ;

  COUNT(*)
----------
        46

Elapsed: 00:00:00.04
SQL> select count(*) from box4 ;

  COUNT(*)
----------
       370

Elapsed: 00:00:00.06
SQL> select count(*) from box5 ;

  COUNT(*)
----------
        44

Elapsed: 00:00:00.04
SQL> select count(*) from box6 ;

  COUNT(*)
----------
        38

Elapsed: 00:00:00.04
SQL> select count(*) from box7 ;

  COUNT(*)
----------
        96

Elapsed: 00:00:00.04
SQL> select count(*) from box8 ;

  COUNT(*)
----------
       486

Elapsed: 00:00:00.07
SQL> select count(*) from box9 ;

  COUNT(*)
----------
        54

Elapsed: 00:00:00.06
SQL>


[Serg]

Hi, jihuyao!
Your method really works, and results are rather impressive (but are still worse than my backtracking solver results ).
Can you post file "pkg_sudoku_new11.sql"? It is interesting in what way you implemented your idea.

I solved all 3 puzzles by my backtracking solver to compare solvers speeds. Here are solution times in seconds.

Code: Select all

        |SQL solver|My solver|
--------+----------+---------+
Puzzle 1|     0.417|    0.020|
Puzzle 2|    79.281|    0.229|
Puzzle 3|     1.034|    0.234|


BTW, my solver found 127 solutions of the first puzzle.

So, you can see SQL solver in the best case (Puzzle 3) is still 4 times slower than backtracking solver. But I expected much worse performance from SQL solver. I am surprised that solving times of your solver varies so substantially for the sample puzzles.

Serg

[jihuyao]

Hi Serg,

That SQL file has too many lines and most of them are not relevant. Here I just copy out the procedures which construct a SQL statement and execute it dynamically. But I can clean up the file and email it to you if necessary.

Basically, the procedures construct a sub SQL statement string for each box by joining the 9 cells in that box one by one and then construct the main SQL statement string by joining the 9 boxes one by one. Similarly, if preferred, one can construct the main SQL statement string by joining the 81 cells one by one.

Code: Select all

procedure get_box_sql(v_box OUT long)
as

begin

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||',';

end loop ;

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

type str_array_1d is table of varchar2(100) index by pls_integer ;
type str_array_2d is table of str_array_1d index by pls_integer ;

array_in         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 ;

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 ;


begin

for i in 1..9 loop

   for j in 1..9 loop

      array_a(i)(j) := '' ;

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

      for m in 1..9 loop   --given n1

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

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

      end loop ;

      for n in 1..9 loop   --given m1
         
         i1 := 1+trunc((m1-1)/3)*3+trunc((n-1)/3) ;
         j1 := 1+mod((m1-1),3)*3+mod((n-1),3) ;

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

      end loop ;

   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 ;


end get_grid_sql ;

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

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

type cur1 is ref cursor ;
c1      cur1 ;

v_grid_sql   long ;
sudoku_str   long ;

begin

get_grid_sql(box_cell_grid, v_grid_sql) ;


open c1 for v_grid_sql ;                                  --return all rows
--open c1 for v_grid_sql||' and rownum=1' ;               --return the first row

loop

   fetch c1 into sudoku_str ;

   exit when c1%rowcount>150 or c1%notfound ;

   dbms_output.put_line(sudoku_str) ;
   
end loop ;

close c1 ;

end get_sudoku_string ;


BTW, I am little lost on puzzle 1. Is it the string below?

Code: Select all

123000000456000000789000000000123000000456000000789000000000123000000456000000789

or alternatively

123000000
456000000
789000000
000123000
000456000
000789000
000000123
000000456
000000789


Happy New Year!

Jihu

[Serg]

Hi, jihuyao!
Thank you for posted PL/SQL procedures (I am familiar with PL/SQL). I'd like to see SQL statements for tables and other objects creation.

How many solutions did you find for Puzzle 1?

I think it is possible (theoretically) to optimize your SQL queries (and maybe table structures). There are well-known optimization tools for Oracle databases - Statspack, trace 10046, etc. Are you familiar with that tools?

Serg

[m_b_metcalf]

How many solutions did you find for Puzzle 1?

I hope:

Code: Select all

brute found 283576 solution(s) in  1.62 seconds. Last was:

 1 2 3 9 6 8 5 7 4
 4 5 6 3 7 2 8 9 1
 7 8 9 5 4 1 6 3 2
 8 6 5 1 2 3 9 4 7
 9 3 7 4 5 6 2 1 8
 2 4 1 7 8 9 3 6 5
 5 7 8 6 9 4 1 2 3
 3 9 2 8 1 7 4 5 6
 6 1 4 2 3 5 7 8 9

Regards,

Mike Metcalf

[Serg]

Hi, jihuyao, Mike!
I see my solver find not all solutions for Puzzle 1. But your SQL solver, jihuyao, seems is working well (at least, Mike Metcalf and you reported the same number of solutions: 283576).
I'll search for bug in my code .

Happy New Year for all!

Serg

[Edited:
P.S. jihuyao, I have some doubt about solving time of Puzzle 1 for your SQL solver. According to your report, PL/SQL procedure executed 0.417 sec, but the next query, reported number of solutions, ran 12 minutes. What we should treat as solving time?]
[Edited 2: I deleted incorrect comparison of SQL solver with Mike Metcalf solver. At the moment I wrote this post I thought SQL solver found all solutions of Puzzle 1 in 0.4 sec, but more correct time of SQL solver solution seems to be 3:33.638 (i.e. 213.638 sec). It much slower than 1.6 sec reported by Mike. Sorry for this mistake.]

[JasonLion]

I also confirm that there are 283,576 solutions to 123000000456000000789000000000123000000456000000789000000000123000000456000000789.

[jihuyao]

My code is in testing mood and I simply enable and/or disable some lines as needed. For puzzle 1, I create a database view named grid based on the constructed SQL statement string without really execute it. eg,

Code: Select all

v_sql := 'create or replace view grid as '||v_grid_sql ;

execute immediate v_sql ;


Then I query the count of the total rows (valid solutions) from the view which takes 12 min.

Code: Select all

select count(*) from grid ;


For puzzle 1, I do not see much SQL tuning to be done except direct joining 81 cells one by one may make some difference. But the performance really depends on the SQL Engine and database resource (and minimum database memory configuration).

For puzzle 2, the join order certainly affects the performance. Roughly, one would like to start with a table with the least rows and join the table with 2nd least rows and so on. But what matters here is that one wants to eliminate the invalid combinations as soon as possible in the 1st join, and then the 2nd join, and so on. Similar to the case with (nested) trial and error, one always wants to eliminate the candidates as many as possible in one trial (so the question is how to find the best starting point for trial and error).

SQL still has uphill battle in performance. But its easy implementation and potential broader applications is already in sight, for example, play with varying strings to find a valid puzzle at different difficulty level.

As Oracle DBA and developer, I will try something more in optimization.

[jihuyao]

Hi Serg,

I found one thing in optimization, the sorting in memory wastes quite bit of time as evidenced in the spool outputs with autotrace enabled. For puzzle 1, timing is 12 min with sorting performed, without sorting it is 3 min (see the one line comment out in the code below).

Code: Select all

procedure get_box_sql(v_box OUT clob)
as

v_cell_sql   clob := '' ;

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 ;

execute immediate 'create or replace view cell as '||v_cell_sql ;                                                 --create a view named cell

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||',';                     --caused sorting in memory
   --v_box := v_box||' (select a as a'||i||' from cell) c'||i||',';                                                --no sorting performed

end loop ;

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 ;


Here are the two outputs with autotrace,

Without sorting

Code: Select all

SQL>
SQL> @c:\temp\pkg_sudoku_new12

Package created.

Elapsed: 00:00:00.02

Package body created.

Elapsed: 00:00:00.04
123......456......789.........123......456......789.........123......456......789                                                                                                                                                                                                                           
---after initialization---                                                                                                                                                                                                                                                                                 
fil_cnt=27                                                                                                                                                                                                                                                                                                 
chg_x_cnt=513                                                                                                                                                                                                                                                                                               
---                                                                                                                                                                                                                                                                                                         
---after some simple techniques applied---                                                                                                                                                                                                                                                                 
fil_cnt=27                                                                                                                                                                                                                                                                                                 
chg_x_cnt=513                                                                                                                                                                                                                                                                                               
---                                                                                                                                                                                                                                                                                                         
start SQL process                                                                                                                                                                                                                                                                                           
total count=283576                                                                                                                                                                                                                                                                                         
end SQL process                                                                                                                                                                                                                                                                                             
Elapsed_time:  00:03:33.638000000                                                                                                                                                                                                                                                                           
---                                                                                                                                                                                                                                                                                                         
---                                                                                                                                                                                                                                                                                                         

PL/SQL procedure successfully completed.

Elapsed: 00:03:33.78
SQL> select count(*) from grid ;

  COUNT(*)                                                                                                                                                                                                                                                                                                 
----------                                                                                                                                                                                                                                                                                                 
    283576                                                                                                                                                                                                                                                                                                 

Elapsed: 00:03:22.68

Statistics
----------------------------------------------------------                                                                                                                                                                                                                                                 
          0  recursive calls                                                                                                                                                                                                                                                                               
          0  db block gets                                                                                                                                                                                                                                                                                 
          0  consistent gets                                                                                                                                                                                                                                                                               
          0  physical reads                                                                                                                                                                                                                                                                                 
          0  redo size                                                                                                                                                                                                                                                                                     
        413  bytes sent via SQL*Net to client                                                                                                                                                                                                                                                               
        400  bytes received via SQL*Net from client                                                                                                                                                                                                                                                         
          2  SQL*Net roundtrips to/from client                                                                                                                                                                                                                                                             
          0  sorts (memory)                                                                                                                                                                                                                                                                                 
          0  sorts (disk)                                                                                                                                                                                                                                                                                   
          1  rows processed                                                                                                                                                                                                                                                                                   



With sorting

Code: Select all

SQL> @c:\temp\pkg_sudoku_new12

Package created.

Elapsed: 00:00:00.02

Package body created.

Elapsed: 00:00:02.35
123......456......789.........123......456......789.........123......456......789                                                                                                                                                                                                                           
---after initialization---                                                                                                                                                                                                                                                                                 
fil_cnt=27                                                                                                                                                                                                                                                                                                 
chg_x_cnt=513                                                                                                                                                                                                                                                                                               
---                                                                                                                                                                                                                                                                                                         
---after some simple techniques applied---                                                                                                                                                                                                                                                                 
fil_cnt=27                                                                                                                                                                                                                                                                                                 
chg_x_cnt=513                                                                                                                                                                                                                                                                                               
---                                                                                                                                                                                                                                                                                                         
start SQL process                                                                                                                                                                                                                                                                                           
total count=283576                                                                                                                                                                                                                                                                                         
end SQL process                                                                                                                                                                                                                                                                                             
Elapsed_time:  00:12:34.104000000                                                                                                                                                                                                                                                                           
---                                                                                                                                                                                                                                                                                                         
---                                                                                                                                                                                                                                                                                                         

PL/SQL procedure successfully completed.

Elapsed: 00:12:34.20
SQL>
SQL> select count(*) from grid ;

  COUNT(*)                                                                                                                                                                                                                                                                                                 
----------                                                                                                                                                                                                                                                                                                 
    283576                                                                                                                                                                                                                                                                                                 

Elapsed: 00:12:01.48

.................................
.................................

Statistics
----------------------------------------------------------                                                                                                                                                                                                                                                 
          0  recursive calls                                                                                                                                                                                                                                                                               
          0  db block gets                                                                                                                                                                                                                                                                                 
          0  consistent gets                                                                                                                                                                                                                                                                               
          0  physical reads                                                                                                                                                                                                                                                                                 
          0  redo size                                                                                                                                                                                                                                                                                     
        413  bytes sent via SQL*Net to client                                                                                                                                                                                                                                                               
        400  bytes received via SQL*Net from client                                                                                                                                                                                                                                                         
          2  SQL*Net roundtrips to/from client                                                                                                                                                                                                                                                             
   60914952  sorts (memory)                                                                                                                                                                                                                                                                                 
          0  sorts (disk)                                                                                                                                                                                                                                                                                   
          1  rows processed                                                                                                                                                                                                                                                                                 


Happy New Year!

Jihu

[Serg]

Hi, all!
I'd like to correct earlier posted my table containing solution times for Puzzles 1,2 posted by jihuyao.
First, I used my another backtracking solver, which is really used by myself during exhaustive search. This solver reports 283576 solutions to Puzzle 1 (123000000456000000789000000000123000000456000000789000000000123000000456000000789).
Second, jihuyao publised 2 puzzles only, but he posted for Puzzle 2 two variants of finding solutions - exhaustive search of all solutions and first found solution (stop after solution finding). I think usually it is not necessary to find all puzzle's solutions when doing exhaustive search etc., but it is important to know - if the puzzle has 1solution or more (I stop solution finding after 2nd solution finding when I am doing exhaustive search). So, I decided to include into the table SQL solver run time when it found all possible solutions (table contains solution times in seconds).

Code: Select all

        |SQL solver|My solver|Mike's solver|
--------+----------+---------+-------------+
Puzzle 1|   213.638|    5.5  |        1.62 |
Puzzle 2|    79.281|    0.073|          -  |


For jihuyao.
I could probably help you with SQL code and tables structures optimization (if you really need any help), but I should have much more detailed description of your code (really - all source code and its description). But unfortunately, I have no enough time to do it now. I am sorry.

Serg