## Solve Every Sudoku without Guessing

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

### Re: Solve Every Sudoku without Guessing

lerxst wrote:[

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

Posts: 27
Joined: 14 September 2011

### Re: Solve Every Sudoku without Guessing

eleven wrote: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.
sdk_fan

Posts: 27
Joined: 14 September 2011

### Re: Solve Every Sudoku without Guessing

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.
eleven

Posts: 1846
Joined: 10 February 2008

### Re: Solve Every Sudoku without Guessing

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 solutionsfrom c1, â€¦â€¦ , c81                                     --join all 81 cell tableswhere a(i) in (1,2,3,4,5,6,7,8,9) and â€¦               --same initial condition set for each celland 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 tableswhere 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.
jihuyao

Posts: 7
Joined: 21 December 2011

### Re: Solve Every Sudoku without Guessing

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
Serg
2018 Supporter

Posts: 606
Joined: 01 June 2010
Location: Russia

### Re: Solve Every Sudoku without Guessing

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_new11Package created.Package body created.123......456......789.........123......456......789.........123......456......789---after initialization---fil_cnt=27chg_x_cnt=513------after some simple techniques applied---fil_cnt=27chg_x_cnt=513---start time for SQL processend time for SQL processElapsed_time:  00:00:00.417000000------PL/SQL procedure successfully completed.Elapsed: 00:00:00.48SQL> SQL> select count(*) from grid ;  COUNT(*)----------    283576Elapsed: 00:12:08.27SQL> `

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

--RatingProgram:dukuso'ssuexrat9
--Rating:10364
--Poster:eleven
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_new11Package created.Elapsed: 00:00:00.05Package 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=22chg_x_cnt=461------after some simple techniques applied---fil_cnt=22chg_x_cnt=465---start time for SQL process123456789457189236968327154249561873576938412831742695314275968695814327782693541end time for SQL processElapsed_time:  00:01:19.281000000------PL/SQL procedure successfully completed.Elapsed: 00:01:19.41SQL> `

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

--RatingProgram:dukuso'ssuexrat9
--Rating:10364
--Poster:eleven
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_new11Package created.Elapsed: 00:00:00.04Package 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=22chg_x_cnt=461------after some simple techniques applied---fil_cnt=22chg_x_cnt=465---start time for SQL process123456789457189236968327154249561873576938412831742695314275968695814327782693541end time for SQL processElapsed_time:  00:00:01.034000000------PL/SQL procedure successfully completed.Elapsed: 00:00:01.13SQL> `

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(*)----------        96Elapsed: 00:00:00.06SQL> select count(*) from box2 ;  COUNT(*)----------       588Elapsed: 00:00:00.10SQL> select count(*) from box3 ;  COUNT(*)----------        46Elapsed: 00:00:00.04SQL> select count(*) from box4 ;  COUNT(*)----------       370Elapsed: 00:00:00.06SQL> select count(*) from box5 ;  COUNT(*)----------        44Elapsed: 00:00:00.04SQL> select count(*) from box6 ;  COUNT(*)----------        38Elapsed: 00:00:00.04SQL> select count(*) from box7 ;  COUNT(*)----------        96Elapsed: 00:00:00.04SQL> select count(*) from box8 ;  COUNT(*)----------       486Elapsed: 00:00:00.07SQL> select count(*) from box9 ;  COUNT(*)----------        54Elapsed: 00:00:00.06SQL> `
jihuyao

Posts: 7
Joined: 21 December 2011

### Re: Solve Every Sudoku without Guessing

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
Serg
2018 Supporter

Posts: 606
Joined: 01 June 2010
Location: Russia

### Re: Solve Every Sudoku without Guessing

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)asbeginv_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)astype 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)asarray_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 ;beginfor 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)astype cur1 is ref cursor ;c1      cur1 ;v_grid_sql   long ;sudoku_str   long ;beginget_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 rowloop   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
`123000000456000000789000000000123000000456000000789000000000123000000456000000789or alternatively123000000456000000789000000000123000000456000000789000000000123000000456000000789`

Happy New Year!

Jihu
jihuyao

Posts: 7
Joined: 21 December 2011

### Re: Solve Every Sudoku without Guessing

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
Serg
2018 Supporter

Posts: 606
Joined: 01 June 2010
Location: Russia

### Re: Solve Every Sudoku without Guessing

Serg wrote: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

m_b_metcalf
2017 Supporter

Posts: 9160
Joined: 15 May 2006
Location: Berlin

### Re: Solve Every Sudoku without Guessing

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.]
Last edited by Serg on Mon Jan 02, 2012 10:15 pm, edited 1 time in total.
Serg
2018 Supporter

Posts: 606
Joined: 01 June 2010
Location: Russia

### Re: Solve Every Sudoku without Guessing

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

JasonLion
2017 Supporter

Posts: 639
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: Solve Every Sudoku without Guessing

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

Posts: 7
Joined: 21 December 2011

### Re: Solve Every Sudoku without Guessing

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)asv_cell_sql   clob := '' ;beginfor 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 cellv_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 performedend 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_new12Package created.Elapsed: 00:00:00.02Package body created.Elapsed: 00:00:00.04123......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.78SQL> select count(*) from grid ;  COUNT(*)                                                                                                                                                                                                                                                                                                  ----------                                                                                                                                                                                                                                                                                                      283576                                                                                                                                                                                                                                                                                                  Elapsed: 00:03:22.68Statistics----------------------------------------------------------                                                                                                                                                                                                                                                            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_new12Package created.Elapsed: 00:00:00.02Package body created.Elapsed: 00:00:02.35123......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.20SQL> 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
jihuyao

Posts: 7
Joined: 21 December 2011

### Re: Solve Every Sudoku without Guessing

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
Serg
2018 Supporter

Posts: 606
Joined: 01 June 2010
Location: Russia

PreviousNext