Do you play Sudoku ?
- by Gilles Haro
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
