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:
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
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.
October 13th, 2009 at 1:19 pm
Anton:
Really very impressive! Well done.
Lucas
October 13th, 2009 at 2:08 pm
Wow!
October 13th, 2009 at 6:16 pm
October 14th, 2009 at 2:37 am
kudoz, I love it
October 14th, 2009 at 2:39 am
select rownum lp
from dual
connect by rownum <= 9
but why connect by? it is old fashion
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
October 22nd, 2009 at 12:17 pm
Powerful ! Can call it Art.
October 22nd, 2009 at 3:01 pm
Anton,
We now shall call you a “Sudoku Master”.
Ittichai
October 31st, 2009 at 2:15 am
fake
October 31st, 2009 at 5:04 am
Impressive! Shared it on Facebook & Twitter.
October 31st, 2009 at 8:36 am
BFD, you can cheat at a game.
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 ‘
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)
October 31st, 2009 at 8:56 pm
C.J. Date would not approve of this abuse.
November 1st, 2009 at 1:08 am
It’s Beautiful.
November 1st, 2009 at 9:31 am
its great , shared on wykop.pl
November 1st, 2009 at 11:54 am
thanks
Game Copy Wizard
November 1st, 2009 at 1:56 pm
Haha… Great.
November 1st, 2009 at 2:48 pm
“Anton,
We now shall call you a “Sudoku Master”.”
Agreed
November 1st, 2009 at 4:24 pm
Very impressive!
November 1st, 2009 at 5:27 pm
that is a genius solution. what happens if the Sudoku has no solution?
November 2nd, 2009 at 6:52 am
yes! very impressive indeed…
November 2nd, 2009 at 10:30 am
Me too impressed