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

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 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
/
```

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

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

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. jareeq says:

Anton this is impressive now you are my third after god and mother 🙂

4. Tonny says:

set lines 9
delete comment #42 😛

5. Ramesh G says:

Wow.. Wonderfull.. Excellent post…

6. great post.

7. Anton Scheffer says:

@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. C says:

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. Anton Scheffer says:

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

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

11. W. G. says:

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. Anton Scheffer says:

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

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.

14. Cafer says:

Very genius Anton! My good friend, ex-colleague 🙂

15. Frank says:

For PostgreSQL, the credits go to Marcin Mank, I only linked to the wiki… 😉

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

17. Anton Scheffer says:

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.

18. Thank you Anton for the solution.

19. Anton Scheffer says:

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

20. Can you do this with MySQL?

21. Anton Scheffer says:

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

22. SRINI says:

Me too impressed

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

24. monty says:

Very impressive!

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

Agreed

26. its great , shared on wykop.pl

27. aleph says:

It’s Beautiful.

28. fooledbyprimes says:

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

29. chithanh says:

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

30. chithanh says:

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

31. David says:

BFD, you can cheat at a game.

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

Ittichai

33. Jean-Marc Desvaux says:

Powerful ! Can call it Art.

34. Anton Scheffer says:

@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

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

but why connect by? it is old fashion 🙂

36. Marco Gralike says:

😉

37. Anton:

Really very impressive! Well done.

Lucas

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

Facebook0TwitterLinkedin  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, […]