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

Share.

1. Great post. Now you can start in an tournament. Anton and his machine.

2. Yesssss!! Now my weekly office sudoku challenges will finally start going my way!!!! :]

3. set lines 9
delete comment #42

4. great post.

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

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

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

8. Its brilliant effort, I tried to convert sudoco query in 10g but I am not getting the correct result..Anybody can help me?????

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

10. Anton Scheffer on

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

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

12. Really amazing !

13. Thanks for your Excellent solutions…now i can win sudoku game

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

15. Thank you Anton for the solution.

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

17. Can you do this with MySQL?

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

19. yes! very impressive indeed…

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

21. “Anton,
We now shall call you a â€œSudoku Masterâ€.”

Agreed

22. Haha… Great.

23. its great , shared on wykop.pl

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

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

27. fake

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

Ittichai

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

30. select rownum lp
from dual
connect by rownum <= 9

but why connect by? it is old fashion

31. kudoz, I love it

32. Wow!

33. Anton:

Really very impressive! Well done.

Lucas