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

16
Share this on .. Tweet about this on TwitterShare on LinkedIn0Share on Facebook0Share on Google+3Email this to someoneShare on Tumblr0Buffer this page

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

Share this on .. Tweet about this on TwitterShare on LinkedIn0Share on Facebook0Share on Google+3Email this to someoneShare on Tumblr0Buffer this page

About Author

Oracle Consultant at AMIS

16 Comments

  1. Sathya Narayanan on

    Great work Anton, I am trying hard to understand this but I have failed every time… Could you please explain the indexing that is  made in the reference model? Thank You

  2. Incroyable, très intéressant et challenge de résoudre une grille de Sudoku avec SQL, chapeau l’artiste.

  3. Does anyone have this in one simple SQL, without it broken up into pieces? I can’t get it to execute.

    I assume I need the first part, select from dual, then the model clause (model reference xxx on …. dimension by (i,j) measures (r), then followed by the “main solve” clause?

    I keep getting syntax errors trying to run it, in 10.2.0.3.

    -Mark

  4. Mike Brandt on

    Well, that was very impressive. I am still working it out .

     

    By the way – if you like sql pluzzles you might like to try this, which can be solved by a single sql statement ( it will work even with Oracle 8i) , assuming you have a table called nums that holds the values 2..100.
    I like this problem , since it is almost impossible to solve by hand. By the way, the answer is the same even if you make the largest value 1000 (and then solving by hand becomes a nightmare).

    efine minval=2
    define maxval=100
    set numwidth 6
    set pages 0
    set feedback off
    set verify off
    column a3 format a3
    column a15 format a15
    column num format 9999
    prompt
    prompt Solve the problem set by:
    prompt
    prompt There are 2 integers a and b between &amp;&amp;minval and &amp;maxval, with a= a.num;

    create view sums as select a+b s,count(*) cc
    from pairs
    group by a+b;

    create view products as select a*b p,count(*) cc
    from pairs
    group by a*b;

    prompt
    prompt Paul: I don't know what the numbers are
    prompt Sam : I knew that. I don't know what the numbers are either
    prompt
    prompt Paul's first statement is more helpful than it first appears
    prompt The pair of numbers cannot be uniquely determined by their product
    prompt This includes not just 2 primes such as 7 and 11,
    prompt but also pairs like 19 and 38, or 4 and 53, 77 and 17
    prompt (assuming we are only looking at 2 digit numbers)
    prompt
    prompt Sam's first statement is even more helpful.
    prompt Sam knows that Paul can't possibly know the numbers
    prompt So whatever his sum is, it cannot
    prompt be formed by a pair that uniquely determines their product
    prompt For example : the sum cannot be 18, or 57 or 94 using the above examples
    prompt
    prompt generate poss_sums as
    prompt the only sums that cannot possibly be made by distinct product pairs
    prompt There are surprisingly few
    pause Ready?

    create view poss_sums as
    select s from sums where cc &gt; 1
    minus
    select pairs.a+pairs.b s from pairs where pairs.a*pairs.b in
    (select p from products where cc=1);

    prompt
    prompt From Sam's first statement the sum must be one of
    prompt
    select s from poss_sums
    order by s;

    prompt
    prompt Paul's last statement:
    prompt Paul: I do now!
    prompt
    prompt So Paul knows that Sam knew that he did not know the numbers and so
    prompt must have a sum matching the above criterion
    prompt This enables him to deduce the pairs.
    prompt So Paul must have a product that decomposes to one of the sums
    prompt in the above list
    prompt in exactly one way (2 or more would not give him a solution and 0
    prompt would violate Sam's previous statement)
    prompt find all products that can have exactly one sum matching the list of sums above
    prompt
    pause Ready?

    create view poss_prods as
    select products.p,max(poss_sums.s) s
    from products,pairs,poss_sums
    where products.cc &gt; 1
    and pairs.a*pairs.b = products.p
    and pairs.a+pairs.b = poss_sums.s
    group by products.p
    having count(poss_sums.s) = 1;

    select 'product is ', p, 'sum is', s from poss_prods
    order by p,s;

    -- now find the sum that has only one possible product fitting that criterion

    prompt
    prompt Sam's last statement:
    prompt Sam : So do I!
    prompt
    prompt So we need to find a sum that only occurs once in the above list
    prompt Otherwise Sam could still not deduce the pair.
    prompt and as we know both the product and the sum we can find the pair
    prompt
    pause Ready?

    col plan_plus_exp for a120
    set lines 160

    select 'In the range' a15,min(num) num,'to' a3,max(num) num from nums;

    set autotrace on explain

    select 'The numbers are' a15, a num,'and' a3, b num
    from pairs,
    ( select max(p) p,s from poss_prods group by s having count(*) = 1) pp
    where pairs.a*pairs.b = pp.p
    and pairs.a+pairs.b= pp.s
    order by a,b;

    set autotrace off

    drop view poss_prods;
    drop view poss_sums;

    drop view products;
    drop view sums;
    drop view pairs;

    prompt
    prompt or to be perverse, and use only in-line views
    pause Ready?
    prompt

    -- using the with clause is much too slow in 10.1
    -- with nums as (select rownum+&amp;&amp;minval-1 num from sys.tab$
    -- where rownum = a.num
    ) pairs,
    ( select max(p) p,s
    from ( select products.p,max(poss_sums.s) s
    from ( select a.num*b.num p,count(*) cc
    from nums a, nums b
    where b.num&gt;= a.num
    group by a.num*b.num
    having count(*) &gt; 1
    ) products,
    ( select a.num a, b.num b
    from nums a, nums b
    where b.num &gt;= a.num
    ) prs,
    (
    select s
    from ( select a.num+b.num s
    from nums a, nums b
    where b.num &gt;= a.num
    group by a.num+b.num
    having count(*) &gt; 1
    ) sums
    minus
    select prs2.a+prs2.b s
    from ( select a.num a, b.num b
    from nums a, nums b
    where b.num &gt;= a.num
    ) prs2
    where prs2.a*prs2.b in
    ( select a.num*b.num p
    from nums a, nums b
    where b.num &gt;= a.num
    group by a.num*b.num
    having count(*) = 1
    )
    ) poss_sums
    where prs.a*prs.b = products.p
    and prs.a+prs.b = poss_sums.s
    group by products.p
    having count(poss_sums.s) = 1
    )
    group by s having count(*) = 1
    ) pp
    where pairs.a*pairs.b = pp.p
    and pairs.a+pairs.b= pp.s
    order by a,b;

    set autotrace off
    set timing off

    drop table nums;

  5. I’m filing this one away for posterity.

    I hope it will work on Oracle 10XE because I would like to have this available to me on my laptop.