Did you know that 11gR2 database could solve a Sudoku puzzle with a single query and, most of the time, and this in less than a second ?

The following query shows you how !
Simply pass a flattened Sudoku grid to it a get the result instantaneously !

col "Solution" format a9
col "Problem" format a9

with Iteration( initialSudoku, Step, EmptyPosition ) as
( select initialSudoku, InitialSudoku, instr( InitialSudoku, '-' ) 
      from ( select '--64----2--7-35--1--58-----27---3--4---------4--2---96-----27--7--58-6--3----18--' InitialSudoku from dual ) 
  union all 
  select initialSudoku
       , substr( Step, 1, EmptyPosition - 1 ) || OneDigit || substr( Step, EmptyPosition + 1 ) 
       , instr( Step, '-', EmptyPosition + 1 ) 
    from Iteration 
       , ( select to_char( rownum ) OneDigit from dual connect by rownum <= 9 ) OneDigit 
   where EmptyPosition > 0 
     and not exists 
        ( select null 
            from ( select rownum IsPossible from dual connect by rownum <= 9 ) 
           where OneDigit = substr( Step, trunc( ( EmptyPosition - 1 ) / 9 ) * 9 + IsPossible, 1 )   -- One line must contain the 1-9 digits 
              or OneDigit = substr( Step, mod( EmptyPosition - 1, 9 ) - 8 + IsPossible * 9, 1 )      -- One row must contain the 1-9 digits 
              or OneDigit = substr( Step, mod( trunc( ( EmptyPosition - 1 ) / 3 ), 3 ) * 3           -- One square must contain the 1-9 digits 
                          + trunc( ( EmptyPosition - 1 ) / 27 ) * 27 + IsPossible 
                          + trunc( ( IsPossible - 1 ) / 3 ) * 6 , 1 ) 
        )
)
select initialSudoku "Problem", Step "Solution" 
  from Iteration 
where EmptyPosition = 0 ;

The Magic thing behind this is called Recursive Subquery Factoring.

The Oracle documentation gives the following definition:
If a subquery_factoring_clause refers to its own query_name in the subquery that defines it, then the subquery_factoring_clause is said to be recursive.
A recursive subquery_factoring_clause must contain two query blocks:
the first is the anchor member and the second is the recursive member.
The anchor member must appear before the recursive member, and it cannot reference query_name.
The anchor member can be composed of one or more query blocks combined by the set operators: UNION ALL, UNION, INTERSECT or MINUS.
The recursive member must follow the anchor member and must reference query_name exactly once.
You must combine the recursive member with the anchor member using the UNION ALL set operator.

This new feature is a replacement of this old Hierarchical Query feature that exists in Oracle since the days of Aladdin (well, at least, release 2 of the database in 1977).
Everyone remembers the old syntax :

select empno, ename, job, mgr, level 
    from   emp 
    start with mgr is null 
    connect by prior empno = mgr;

that could/should be rewritten (but not as often as it should) as

withT_Emp (empno, name, level) as 
      ( select empno, ename, job, mgr, level 
           from   emp 
           start with mgr is null 
           connect by prior empno = mgr 
      )
select * from   T_Emp;

which uses the "with" syntax, whose main advantage is to clarify the readability of the query.

Although very efficient, this syntax had the disadvantage of being a Non-Ansi Sql Syntax.
Ansi-Sql version of Hierarchical Query is called Recursive Subquery Factoring.
As of 11gR2, Oracle got compliant with Ansi Sql and introduced Recursive Subquery Factoring. It is basically an extension of the "With" clause that enables recursion.

Now, the new syntax for the query would be

with T_Emp (empno, name, job, mgr, hierlevel) as 
     ( select E.empno, E.ename, E.job, E.mgr, 1 from emp E where E.mgr is null 
       union all 
       select E.empno, E.ename, E.job, E.mgr, T.hierlevel + 1from emp E 
                                                                                                          join T_Emp T on ( E.mgr = T.empno )
)
select * from   T_Emp;

The anchor member is a replacement for the "start with"
The recursive member is processed through iterations.
It joins the Source table (EMP) with the result from the Recursive Query itself (T_Emp)
Each iteration works with the results of all its preceding iterations.
    Iteration 1 works on the results of the first query
    Iteration 2 works on the results of Iteration 1 and first query
    Iteration 3 works on the results of Iteration 1, Iteration 2 and first query.

So, knowing that, the Sudoku query it self-explaining;
The anchor member contains the "Problem" : The Initial Sudoku and the Position of the first "hole" in the grid.
The recursive member tries to replace the considered hole with any of the 9 digit that would satisfy the 3 rules of sudoku
Recursion progress through the grid until it is complete.

Another example :  Fibonaccy Numbers :  un = (un-1) + (un-2)
with Fib (u1, u2, depth) as
  (select 1, 1, 1 from dual
   union all
   select u1+u2, u1, depth+1 from Fib where depth<10)
select u1 from Fib;

Conclusion
Oracle brings here a new feature (which, to be honest, already existed on other concurrent systems) and extends the power of the database to new boundaries. It’s now up to developers to try and test it and find more useful application than solving puzzles…
But still, solving a Sudoku in less time it takes to say it remains impressive…

Interesting links:

You might be interested by the following links which cover different aspects of this feature

Oracle Documentation
Lucas Jellema 's Blog
Fibonaci Numbers