Recursive With Clause

with x( s, ind ) as
( select sud, instr( sud, ' ' )
  from ( select 
  '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79'
  sud from dual )
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  from x
     , ( select to_char( rownum ) z
         from dual
         connect by rownum <= 9
       ) z
  where ind > 0
  and not exists ( select null
                   from ( select rownum lp
                          from dual
                          connect by rownum <= 9
                        )
                   where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0
/

(Anton Scheffer) [Solving a Sudoku using Recursive Subquery Factoring]

Impressive code from our amici over at Amis. But also an impressive example of how far one can go outside the original domain of a language. I mean recursive queries? On the other hand this algorithm does not look too good in Scala or in Perl either. The mathematics of Sudoku are studied in depth. Sudoku has been shown to be NP-complete and of the many ways of solving Sudoku, dancing links and constraint programming seem to be very popular. (Typically, it takes milli seconds for a computer to solve a Sudoku.)


  1. Well, that was very impressive. I am still winrokg it out . By the way if you like sql pluzzles you might like to try this, which can be solved by a single sql statement ( it will work even with Oracle 8i) , assuming you have a table called nums that holds the values 2..100.I like this problem , since it is almost impossible to solve by hand. By the way, the answer is the same even if you make the largest value 1000 (and then solving by hand becomes a nightmare).efine minval=2define maxval=100set numwidth 6set pages 0set feedback offset verify offcolumn a3 format a3column a15 format a15column num format 9999promptprompt Solve the problem set by:promptprompt There are 2 integers a and b between amp; amp;minval and amp;maxval, with a= a.num;create view sums as select a+b s,count(*) cc from pairs group by a+b; create view products as select a*b p,count(*) cc from pairs group by a*b;promptprompt Paul: I don’t know what the numbers areprompt Sam : I knew that. I don’t know what the numbers are eitherpromptprompt Paul’s first statement is more helpful than it first appearsprompt The pair of numbers cannot be uniquely determined by their productprompt This includes not just 2 primes such as 7 and 11, prompt but also pairs like 19 and 38, or 4 and 53, 77 and 17prompt (assuming we are only looking at 2 digit numbers)promptprompt Sam’s first statement is even more helpful.prompt Sam knows that Paul can’t possibly know the numbersprompt So whatever his sum is, it cannot prompt be formed by a pair that uniquely determines their productprompt For example : the sum cannot be 18, or 57 or 94 using the above examplespromptprompt generate poss_sums as prompt the only sums that cannot possibly be made by distinct product pairsprompt There are surprisingly fewpause Ready?create view poss_sums as select s from sums where cc gt; 1 minus select pairs.a+pairs.b s from pairs where pairs.a*pairs.b in (select p from products where cc=1);promptprompt From Sam’s first statement the sum must be one ofpromptselect s from poss_sumsorder by s;promptprompt Paul’s last statement:prompt Paul: I do now!promptprompt So Paul knows that Sam knew that he did not know the numbers and so prompt must have a sum matching the above criterionprompt This enables him to deduce the pairs.prompt So Paul must have a product that decomposes to one of the sums prompt in the above listprompt in exactly one way (2 or more would not give him a solution and 0 prompt would violate Sam’s previous statement)prompt find all products that can have exactly one sum matching the list of sums abovepromptpause Ready?create view poss_prods asselect products.p,max(poss_sums.s) s from products,pairs,poss_sumswhere products.cc gt; 1 and pairs.a*pairs.b = products.p and pairs.a+pairs.b = poss_sums.sgroup by products.phaving count(poss_sums.s) = 1;select ‘product is ‘, p, ‘sum is’, s from poss_prodsorder by p,s; — now find the sum that has only one possible product fitting that criterion prompt prompt Sam’s last statement:prompt Sam : So do I!prompt prompt So we need to find a sum that only occurs once in the above listprompt Otherwise Sam could still not deduce the pair.prompt and as we know both the product and the sum we can find the pairpromptpause Ready?col plan_plus_exp for a120set lines 160select ‘In the range’ a15,min(num) num,’to’ a3,max(num) num from nums;set autotrace on explainselect ‘The numbers are’ a15, a num,’and’ a3, b numfrom pairs, ( select max(p) p,s from poss_prods group by s having count(*) = 1) ppwhere pairs.a*pairs.b = pp.p and pairs.a+pairs.b= pp.sorder by a,b;set autotrace offdrop view poss_prods;drop view poss_sums;drop view products;drop view sums;drop view pairs;promptprompt or to be perverse, and use only in-line viewspause Ready?prompt– using the with clause is much too slow in 10.1– with nums as (select rownum+ amp; amp;minval-1 num from sys.tab$– where rownum = a.num ) pairs, ( select max(p) p,s from ( select products.p,max(poss_sums.s) s from ( select a.num*b.num p,count(*) cc from nums a, nums b where b.num gt;= a.num group by a.num*b.num having count(*) gt; 1 ) products, ( select a.num a, b.num b from nums a, nums b where b.num gt;= a.num ) prs, ( select s from ( select a.num+b.num s from nums a, nums b where b.num gt;= a.num group by a.num+b.num having count(*) gt; 1 ) sums minus select prs2.a+prs2.b s from ( select a.num a, b.num b from nums a, nums b where b.num gt;= a.num ) prs2 where prs2.a*prs2.b in ( select a.num*b.num p from nums a, nums b where b.num gt;= a.num group by a.num*b.num having count(*) = 1 ) ) poss_sums where prs.a*prs.b = products.p and prs.a+prs.b = poss_sums.s group by products.p having count(poss_sums.s) = 1 ) group by s having count(*) = 1 ) ppwhere pairs.a*pairs.b = pp.p and pairs.a+pairs.b= pp.sorder by a,b;set autotrace offset timing offdrop table nums;

Leave a Reply