AMIS website AMIS werkenbij weblog Technology School Contact
TECHNOLOGY.AMIS.nl

## Oracle RDBMS 11gR2 - Solving a Sudoku using Recursive Subquery Factoring by Anton Scheffer

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
    /

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

? X

Even More | More »
This entry was posted on Tuesday, October 13th, 2009 at 11:11 am and is filed under Database, Devel. + PL/SQL tools, General, Oracle. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

### 23 Responses to “Oracle RDBMS 11gR2 - Solving a Sudoku using Recursive Subquery Factoring”

1. Lucas Jellema Says:
   October 13th, 2009 at 1:19 pm

   Anton:

   Really very impressive! Well done.

   Lucas

2. Rob van Wijk Says:
   October 13th, 2009 at 2:08 pm

   Wow!

3. Marco Gralike Says:
   October 13th, 2009 at 6:16 pm

4. Laurent Schneider Says:
   October 14th, 2009 at 2:37 am

   kudoz, I love it

5. Laurent Schneider Says:
   October 14th, 2009 at 2:39 am

   select rownum lp
   from dual
   connect by rownum <= 9

   but why connect by? it is old fashion

6. Anton Scheffer Says:
   October 14th, 2009 at 8:32 am

   @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

7. Jean-Marc Desvaux Says:
   October 22nd, 2009 at 12:17 pm

   Powerful ! Can call it Art.

8. Ittichai Chammavanijakul Says:
   October 22nd, 2009 at 3:01 pm

   Anton,
   We now shall call you a “Sudoku Master”.

   Ittichai

9. Jack Hewitt Says:
   October 31st, 2009 at 2:15 am

   fake

10. Prakash Murthy Says:
    October 31st, 2009 at 5:04 am

    Impressive! Shared it on Facebook & Twitter.

11. David Says:
    October 31st, 2009 at 8:36 am

    BFD, you can cheat at a game.

12. chithanh Says:
    October 31st, 2009 at 2:08 pm

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

13. chithanh Says:
    October 31st, 2009 at 2:11 pm

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

14. fooledbyprimes Says:
    October 31st, 2009 at 8:56 pm

    C.J. Date would not approve of this abuse.

15. aleph Says:
    November 1st, 2009 at 1:08 am

    It’s Beautiful.

16. Helpers Says:
    November 1st, 2009 at 9:31 am

    its great , shared on wykop.pl

17. raiz Says:
    November 1st, 2009 at 11:54 am

    thanks

    Game Copy Wizard

18. covalic Says:
    November 1st, 2009 at 1:56 pm

    Haha… Great.

19. sal Says:
    November 1st, 2009 at 2:48 pm

    “Anton,
    We now shall call you a “Sudoku Master”.”

    Agreed

20. monty Says:
    November 1st, 2009 at 4:24 pm

    Very impressive!

21. club penguin toys Says:
    November 1st, 2009 at 5:27 pm

    that is a genius solution. what happens if the Sudoku has no solution?

22. daily sudoku Says:
    November 2nd, 2009 at 6:52 am

    yes! very impressive indeed…

23. SRINI Says:
    November 2nd, 2009 at 10:30 am

    Me too impressed

### Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

Spam protection: Sum of 1 + 9 ?