Solving a Sudoku with 1 SQL-statement: the Model-clause 20188367001

Solving a Sudoku with 1 SQL-statement: the Model-clause

Solving a Suduku with one SQL-statement, is that possible? A lot of people won’t believe it, but yes, it can be done.
I did already a blog on Solving a Sudoku with Collections, but for this blog I used another aproach: the model clause. The model clause is introduced in Oracle 10g and, according to the documentation “brings a new level of power and flexibility to SQL calculations”. And that isn’t too much said! But how can you use it for solving Sudokus? Quit simple in fact , select it as a string from 81 characters from dual

select '   56  2 ' || 
       ' 63      ' || 
       '   2   37' || 
       ' 5    173' || 
       '327  14  ' || 
       '  1  9   ' || 
       '6   7    ' || 
       '    2 381' || 
       '83       ' s
from dual

and add the model clause.

  model
    reference xxx on
      ( select i, j, r
        from dual
        model
          dimension by ( 1 i, 1 j )
          measures ( 1 x, 1 y, 1 r )
          rules
            ( x[for i from 1 to 81 increment 1, 1] = trunc( ( cv(i) - 1 ) / 9 ) * 9
            , y[for i from 1 to 81 increment 1, 1] = mod( cv(i) - 1, 9 ) + 1
            , r[for i from 1 to 81 increment 1, for j from 1 to 8 increment 1] = case when x[ cv(i), 1 ] + cv(j) < cv(i)
                                                                                   then x[ cv(i), 1 ] + cv(j)
                                                                                   else x[ cv(i), 1 ] + cv(j) + 1
                                                                                 end
            , r[for i from 1 to 81 increment 1, for j from 9 to 16 increment 1] = case when y[ cv(i), 1 ] + ( cv(j) - 9 ) * 9 < cv(i)
                                                                                    then y[ cv(i), 1 ] + ( cv(j) - 9 ) * 9
                                                                                    else y[ cv(i), 1 ] + ( cv(j) - 8 ) * 9
                                                                                  end
            , r[for i from 1 to 81 increment 1, 17] = case mod( x[ cv(i), 1 ] / 9, 3 )
                                                        when 0 then x[ cv(i), 1 ] + 9
                                                        when 1 then x[ cv(i), 1 ] - 9
                                                        when 2 then x[ cv(i), 1 ] - 18
                                                      end + mod( y[ cv(i), 1 ], 3 ) + trunc( (y[ cv(i), 1 ] - 1) / 3 ) * 3 + 1
            , r[for i from 1 to 81 increment 1, 18] = case mod( x[ cv(i), 1 ] / 9, 3 )
                                                        when 0 then x[ cv(i), 1 ] + 18
                                                        when 1 then x[ cv(i), 1 ] + 9
                                                        when 2 then x[ cv(i), 1 ] - 9
                                                      end + mod( y[ cv(i), 1 ], 3 ) + trunc( (y[ cv(i), 1 ] - 1) / 3 ) * 3 + 1
            , r[for i from 1 to 81 increment 1, 19] = case mod( x[ cv(i), 1 ] / 9, 3 )
                                                        when 0 then x[ cv(i), 1 ] + 9
                                                        when 1 then x[ cv(i), 1 ] - 9
                                                        when 2 then x[ cv(i), 1 ] - 18
                                                      end + mod( y[ cv(i), 1 ] + 1, 3 ) + trunc( (y[ cv(i), 1 ] - 1) / 3 ) * 3 + 1
            , r[for i from 1 to 81 increment 1, 20] = case mod( x[ cv(i), 1 ] / 9, 3 )
                                                        when 0 then x[ cv(i), 1 ] + 18
                                                        when 1 then x[ cv(i), 1 ] + 9
                                                        when 2 then x[ cv(i), 1 ] - 9
                                                      end + mod( y[ cv(i), 1 ] + 1, 3 ) + trunc( (y[ cv(i), 1 ] - 1) / 3 ) * 3 + 1
            )
      ) dimension by ( i, j ) measures ( r )

I use a reference model, which in turn is a SQL-query with a model clause. In a Sudoku can a certain number occur only once on every row, every column and every block. This reference model gives me for every cell in the Sudoku the numbers, that is the index in my Sudoku string, of the others cells on the same row, the same column and the same block. And that is all we need for the main model.

    main solve
      dimension by ( 1 x )
      measures ( cast( s as varchar2(81) ) s
               , 1 i
               , 1 j
               , 0 d
               , cast( '' as varchar2(20) ) v
               )
      rules iterate ( 100000 ) until ( length( replace( s[1], ' ' ) ) >= 81 or d[1] + 81 < iteration_number )
            ( i[1] = instr( s[1], ' ', j[1] )
            , v[1] = translate( '123456789'
                              , '#' ||
                                substr( s[1], xxx.r[ i[1], 1], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 2], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 3], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 4], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 5], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 6], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 7], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 8], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 9], 1 ) ||
                                substr( s[1], xxx.r[ i[1],10], 1 ) ||
                                substr( s[1], xxx.r[ i[1],11], 1 ) ||
                                substr( s[1], xxx.r[ i[1],12], 1 ) ||
                                substr( s[1], xxx.r[ i[1],13], 1 ) ||
                                substr( s[1], xxx.r[ i[1],14], 1 ) ||
                                substr( s[1], xxx.r[ i[1],15], 1 ) ||
                                substr( s[1], xxx.r[ i[1],16], 1 ) ||
                                substr( s[1], xxx.r[ i[1],17], 1 ) ||
                                substr( s[1], xxx.r[ i[1],18], 1 ) ||
                                substr( s[1], xxx.r[ i[1],19], 1 ) ||
                                substr( s[1], xxx.r[ i[1],20], 1 )
                              , '#' )
            , j[1] = case
                       when j[1] >= 81 then 1
                       else j[1] + 1
                     end
            , s[1] = case
                       when length( v[1] ) = 1 then substr( s[1], 1, i[1] - 1 ) || v[1] || substr( s[1], i[1] + 1 )
                       else s[1]
                     end
            , d[1] = case
                       when length( v[1] ) = 1 then iteration_number
                       else d[1]
                     end
            )

And that means: find the first unsolved cell, starting from cell j

            ( i[1] = instr( s[1], ' ', j[1] )

for this cell, check the values from the other cells on the same row, column, block and find the possible values for this cell with the translate

            , v[1] = translate( '123456789'
                              , '#' ||
                                substr( s[1], xxx.r[ i[1], 1], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 2], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 3], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 4], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 5], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 6], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 7], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 8], 1 ) ||
                                substr( s[1], xxx.r[ i[1], 9], 1 ) ||
                                substr( s[1], xxx.r[ i[1],10], 1 ) ||
                                substr( s[1], xxx.r[ i[1],11], 1 ) ||
                                substr( s[1], xxx.r[ i[1],12], 1 ) ||
                                substr( s[1], xxx.r[ i[1],13], 1 ) ||
                                substr( s[1], xxx.r[ i[1],14], 1 ) ||
                                substr( s[1], xxx.r[ i[1],15], 1 ) ||
                                substr( s[1], xxx.r[ i[1],16], 1 ) ||
                                substr( s[1], xxx.r[ i[1],17], 1 ) ||
                                substr( s[1], xxx.r[ i[1],18], 1 ) ||
                                substr( s[1], xxx.r[ i[1],19], 1 ) ||
                                substr( s[1], xxx.r[ i[1],20], 1 )
                              , '#' )

and if only one value is possible we have solved this cell

            , s[1] = case
                       when length( v[1] ) = 1 then substr( s[1], 1, i[1] - 1 ) || v[1] || substr( s[1], i[1] + 1 )
                       else s[1]
                     end

and do this again and again until we have solved the complete Sudoku or don’t find anything to solve

      rules iterate ( 100000 ) until ( length( replace( s[1], ' ' ) ) >= 81 or d[1] + 81 < iteration_number )

Put this all together, and you have a query wich can solve only “simple” Sudokus. A slightly more complex version solves every possible Soduku, by trying every possible value in a cell, and try another possible value if the first gues proves to be wrong.

    rules iterate ( 999999 ) until ( length( replace( s[1], ' ' ) ) >= 81 )
          ( i[ it[1] ] = case
                           when m[1] = 1 then instr( s[1], ' ' )
                           else i[ cv() ]
                         end
          , v[ it[1] ] = case
                           when m[1] = 1 then
                             translate( '123456789'
                                , '#' ||
                                  substr( s[1], xxx.r[ i[cv()], 1], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 2], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 3], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 4], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 5], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 6], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 7], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 8], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()], 9], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],10], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],11], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],12], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],13], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],14], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],15], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],16], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],17], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],18], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],19], 1 ) ||
                                  substr( s[1], xxx.r[ i[cv()],20], 1 )
                                , '#' )
                           else v[ cv() ]
                         end
          , m[1] = nvl2( v[ it[1] ], m[1], 0 )
          , it[1] = case
                      when m[1] = 1 then it[1]
                      else it[1] - 1
                    end
          , j[ it[1] ] = case
                           when m[1] = 1 then 1
                           else j[ cv() ] + 1
                         end
          , m[1] = case
                        when length( v[ it[1] ] ) >= j[ it[1] ] then 1
                        else m[1]
                      end
          , s[1] = case
                      when m[1] = 1 then substr( s[1], 1, i[ it[1] ] - 1 ) || substr( v[ it[1] ], j[ it[1] ], 1 ) || substr( s[1], i[ it[1] ] + 1 )
                      else substr( s[1], 1, i[ it[1] ] - 1 ) || ' ' || substr( s[1], i[ it[1] ] + 1 )
                   end
          , it[1] = case
                      when m[1] = 1 then it[1] + 1
                      else it[1]
                    end
          )

This query can take some more time, up to 60 seconds.

These queries should work on every 10G database, but I have tested it only on 10.2.0.1.0, and I have heard that they won’t work on 10.2.0.3.0

Anton

code

Tags:,

16 Comments

  1. John February 15, 2012
  2. Sathya Narayanan September 28, 2010
  3. Anton Scheffer February 19, 2009
  4. Theo February 18, 2009
  5. Sudoku August 13, 2008
  6. Anton Scheffer November 21, 2007
  7. Mark Bobak November 20, 2007
  8. Mark Bobak November 20, 2007
  9. Franco June 12, 2007
  10. Garry June 11, 2007
  11. Nik June 9, 2007
  12. Mike Brandt June 6, 2007
  13. Patrick Sinke June 5, 2007
  14. nikola June 5, 2007
  15. Marco Gralike June 5, 2007
  16. grant czerepak June 5, 2007