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:
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
Great post. Now you can start in an tournament. Anton and his machine.
Yesssss!! Now my weekly office sudoku challenges will finally start going my way!!!! :]
Anton this is impressive now you are my third after god and mother 🙂
set lines 9
before your query you get a nice column like your puzzle.
delete comment #42 😛
Wow.. Wonderfull.. Excellent post…
great post.
@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.
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.
@W.G. Nice 🙂
@Bijesh K Recursive subfactoring is something Oracle introduced in 11GR2, so you can’t convert this kind of solutions to 10g.
Its brilliant effort, I tried to convert sudoco query in 10g but I am not getting the correct result..Anybody can help me?????
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
;
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.
Really amazing !
Very genius Anton! My good friend, ex-colleague 🙂
For PostgreSQL, the credits go to Marcin Mank, I only linked to the wiki… 😉
Thanks for your Excellent solutions…now i can win sudoku game 🙂
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.
Ported using T-SQL @ http://michaelhthomasblog.blogspot.com/2009/11/solving-sudoku-using-recursive-common.html
Thank you Anton for the solution.
Great work!
Your work has been ported to PostgreSQL as well: http://wiki.postgresql.org/wiki/Sudoku_puzzle
@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.
Can you do this with MySQL?
@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.
Me too impressed
yes! very impressive indeed…
that is a genius solution. what happens if the Sudoku has no solution?
Very impressive!
“Anton,
We now shall call you a “Sudoku Masterâ€.”
Agreed
Haha… Great.
its great , shared on wykop.pl
It’s Beautiful.
C.J. Date would not approve of this abuse.
Hm. Seems that the comment system ate the spaces.
‘…………………1.2…..1…2………….2…1…..2.1…………………’ (replace dots with spaces)
I wonder what happens if you input a Sudoku that has no solution like
‘ 1 2 1 2 2 1 2 1 ‘
BFD, you can cheat at a game.
Impressive! Shared it on Facebook & Twitter.
fake
Anton,
We now shall call you a “Sudoku Master”.
Ittichai
Powerful ! Can call it Art.
@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
select rownum lp
from dual
connect by rownum <= 9
but why connect by? it is old fashion 🙂
kudoz, I love it
😉
Wow!
Anton:
Really very impressive! Well done.
Lucas