Oracle RDBMS 11gR2 – Solving a Sudoku using Recursive Subquery Factoring

45

Oracle Database 11g Release 2 introduces a new feature called Recursive Subquery Factoring. My collegue Lucas sees it as a substitute for Connect By based hierarchical querying, Oracle RDBMS 11gR2 – new style hierarchical querying using Recursive Subquery Factoring. When I first was thinking about a pratical use for this feature I couldn’t come up with anything, but on second thought:: solving Sudokus!

Say you have a sudoku like:

 To solve this sudoku you first have to transforms this to a single string by appending all rows together:

"53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79"

Past this string into a Recursive Subquery, run it and you get a new string with your solved sudoku:

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
/

sqlplus

This string can be transformed back to a nice display of the solution

 

So with Recursive Subquery Factoring you can solve your sudokus in 1 statement wich does fit on your screen, not something like in Solving a Sudoku with 1 SQL-statement: the Model-clause

 

Anton

Share.

About Author

45 Comments

  1. Anton Scheffer on

    @c: Maybe it suffices to find one solutions, this query finds all solutions.  And that has nothing to do with breadth- or depth-first searching,  that’s because there’s no way to stop the recursion after finding a solution.

  2. It looks to me that what the recursive subquery does is “breadth-first search”, i.e., for each blank square in the sudoku, it considers all possibilities before moving on to the next blank square. That computes all solutions to the sudoku, but I’m wondering if that is a good way of solving a sudoku in practice because it generally suffices to find one solution.

  3. Anton Scheffer on

    @W.G. Nice :)
    @Bijesh K Recursive subfactoring is something Oracle introduced in 11GR2, so you can’t convert this kind of solutions to 10g.

  4. Inspired by your example, I did the Tower of Hanoi:

    with h(x, n, a, b, c) as (
    select 0, 3, ‘A’, ‘B’, ‘C’ from dual
    union all
    select x+m*power(2,n), n-1, decode(m, 1, b, a)
    , decode(m, 1, a, c), decode(m, 1, c, b)
    from h, (select -1 m from dual union all select 1 from dual)
    where n > 1
    )
    select ‘move disk ‘ || n || ‘ from ‘ || a || ‘ to ‘ || c solution
    from h order by x
    ;

  5. My method solves all sudokus. It’s a brute force solver, so it doesn’t need any clever strategies.

  6. how ever this dosen’t resolve all the sudoku types ..maybe just the easy ones.. for a more detailed explanation check this sudoku solver that also contains some strategies used by sudoku experts. http://www.scanraid.com/sudoku.htm . For example i dunno how your algorithm would resolve the Intersection Removal Strategy called also the Pointing Pairs Strategy.

  7. Anton Scheffer on

    I had no idea that Oracle was so late with its recursive queries. Those ports in PostgreSQL and T-SQL look very similar to my solution. I’m impressed, both by the possiblities from those languages as by the porting qualities of Frank and Mike.

  8. Anton Scheffer on

    @Dan
    I don’t know anything about MySQL, but I don’t think this query will run unchanged on any database except the latest Oracle 11gR2.

  9. Anton Scheffer on

    @chithanh and @club penguin toys
    If the Sudoku has no solutions the result of the query is “no rows selected”. But it can take a lot of time before you get that result, I stopped it after 5 minutes using the suggestions of chithanh.
    If the sudoku has more solutions, every solutions is shown.

  10. Hm. Seems that the comment system ate the spaces.
    ‘…………………1.2…..1…2………….2…1…..2.1…………………’ (replace dots with spaces)

  11. I wonder what happens if you input a Sudoku that has no solution like
    ‘ 1 2 1 2 2 1 2 1 ‘

  12. Anton Scheffer on

    @Laurent: I’ve tried the also some other number generators:

    select *
    from table( sys.odcinumberlist( 1, 2, 3, 4, 5, 6, 7, 8, 9 ) )
    /

    select *
    from ( with x( r ) as
    ( select 1 r from dual
    union all
    select r + 1
    from x
    where r < 9
    )
    select * from x
    )
    /

    But, being nearly 50, I stuck with the old fashioned way