Tuesday, November 23, 2021

Fun - Sudoku Solver

Once upon a time, SUDOKU was a popular puzzle. The following query will attempt to solve a puzzle that is entered towards the top of this query. You'll need to enter the given numbers in their proper locations; the "-" represents an empty box. Note that this query is a very clever implementation of a 'recursive-WITH'. Have fun!

  

   with  
     sudoku_solver ( sol_str, ind )  as
       ( select  sud
              ,  instr( sud, '-' )
           from  ( select  '6--9-1--8'  -- Row #1
                       ||  '-4--8--3-'  -- Row #2
                       ||  '---4-6---'  -- Row #3
                       ||  '-9-----7-'  -- Row #4
                       ||  '5-7-1-2-9'  -- Row #5
                       ||  '-3-----5-'  -- Row #6
                       ||  '---1-2---'  -- Row #7
                       ||  '-1--5--9-'  -- Row #8
                       ||  '7--8-9--2'  -- Row #9
                       as  sud 
                     from dual 
                 )
       union all
         select  substr( sol_str, 1, ind - 1 ) || z 
             ||  substr( sol_str, ind + 1 )
              ,  instr( sol_str, '-', ind + 1 )
           from  sudoku_solver   
              ,  ( select  to_char( rownum ) z  
                     from  dual  connect by rownum <= 9 ) z
          where  ind > 0
            and  not exists 
              ( select  1
                  from  (select rownum lp from dual connect by rownum <= 9)
                 where  z = substr(sol_str, trunc((ind-1)/9)*9+lp, 1)
                    or  z = substr(sol_str, mod(ind-1, 9)-8+lp*9, 1)
                    or  z = substr(sol_str, mod(trunc((ind-1)/3), 3)*3+
                              trunc((ind-1)/27)*27+lp+trunc((lp-1)/3)*6, 1)
             )
       )
   , results  as  (select sol_str from sudoku_solver where ind = 0 )
   SELECT  'Row #' || rownum                as "Row Number"
        ,  substr(sol_str, rownum*9-8, 9)   as "Solution"
     from  results connect by level <= 9 ;
  

Note: this code is not the product of my brain-steam. I found this algorithm somewhere on the web and have enjoyed playing with it. I apologize for not remembering where or who originally came up with it; but, my hat is off to them!

No comments:

Post a Comment