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

Anton Scheffer October 13, 2009 45
0 0
Read Time:1 Minute, 47 Second

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 a Sudoku!

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

About Post Author

Anton Scheffer

Oracle Consultant at AMIS
anton.scheffer@amis.nl
Happy
Happy
0 %
Sad
Sad
0 %
Excited
Excited
0 %
Sleepy
Sleepy
0 %
Angry
Angry
0 %
Surprise
Surprise
0 %

Related posts:

Default ThumbnailWriting a Word Search puzzle solver in SQL Default ThumbnailAnalyzing Match Scores in ‘fuzzy searches’ – explaining the shades of gray in a non-binary world Default ThumbnailOracle Database Cross Session Data Cache – Introducing the Globally Accessible Database Context Oracle SQL and PL/SQL: juggling with user defined types (ADT) and XMLType – for creating an ADT based XML Service API Data Integriteit anno 2011 – Hands-on met Toon Koppelaars en RuleGen 3.0 bij AMIS op dinsdag 27 september

Average Rating

5 Star
0%
4 Star
0%
3 Star
0%
2 Star
0%
1 Star
0%
(Add your review)

45 thoughts on “Oracle RDBMS 11gR2 – Solving a Sudoku using Recursive Subquery Factoring”

  4. set lines 9
    before your query you get a nice column like your puzzle.
    delete comment #42 😛

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

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

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

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

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

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

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

  21. @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.

  23. @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.

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

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

  40. @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

Comments are closed.

Next Post

OOW 2009: The killer feature of Oracle Database 11gR2 - Edition Based Redefinition (or database object versioning)

Tue Oct 13 , 2009
  Today I presented on what is possibly the hottest story on the Oracle Database 11gR2 release: Edition Based Redefinition (EBR). EBR allows us to add a whole new dimension to the database – the Edition (that complements the existing dimensions of schema and object type). Every database object (well, […]

You May Like

%d bloggers like this: