# 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```

```  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, ' ' ) ) >= 81 or d + 81 < iteration_number )
( i = instr( s, ' ', j )
, v = translate( '123456789'
, '#' ||
substr( s, xxx.r[ i, 1], 1 ) ||
substr( s, xxx.r[ i, 2], 1 ) ||
substr( s, xxx.r[ i, 3], 1 ) ||
substr( s, xxx.r[ i, 4], 1 ) ||
substr( s, xxx.r[ i, 5], 1 ) ||
substr( s, xxx.r[ i, 6], 1 ) ||
substr( s, xxx.r[ i, 7], 1 ) ||
substr( s, xxx.r[ i, 8], 1 ) ||
substr( s, xxx.r[ i, 9], 1 ) ||
substr( s, xxx.r[ i,10], 1 ) ||
substr( s, xxx.r[ i,11], 1 ) ||
substr( s, xxx.r[ i,12], 1 ) ||
substr( s, xxx.r[ i,13], 1 ) ||
substr( s, xxx.r[ i,14], 1 ) ||
substr( s, xxx.r[ i,15], 1 ) ||
substr( s, xxx.r[ i,16], 1 ) ||
substr( s, xxx.r[ i,17], 1 ) ||
substr( s, xxx.r[ i,18], 1 ) ||
substr( s, xxx.r[ i,19], 1 ) ||
substr( s, xxx.r[ i,20], 1 )
, '#' )
, j = case
when j >= 81 then 1
else j + 1
end
, s = case
when length( v ) = 1 then substr( s, 1, i - 1 ) || v || substr( s, i + 1 )
else s
end
, d = case
when length( v ) = 1 then iteration_number
else d
end
)
```

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

```            ( i = instr( s, ' ', j )
```

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

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

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

## 16 thoughts on “Solving a Sudoku with 1 SQL-statement: the Model-clause”

1. John says:

This is a nice way to import a Sudoku puzzle.

Try integrating it with a user interface like this example: http://www.vantasyworld.com/fun/sudoku/sudokusolver.html.

Does it also detect sudoku puzzles that are impossible to solve?

2. Sathya Narayanan says:

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

3. Anton Scheffer says:

My solver can solve any solvable sudoku.

4. Theo says:

I am impressed to solve a Sudoku in one statement but how about solving complex Sudokus can it handle all?

http://vbaexcel.eu/vba-macro-code/sudoku-solver

This solver I have been using works fine but it is alot of code compared to yours!

5. Sudoku says:

Incroyable, trÃ¨s intÃ©ressant et challenge de rÃ©soudre une grille de Sudoku avec SQL, chapeau l’artiste.

6. Mark Bobak says:

Never mind….just saw the comment about not working in 10.2.0.3…..sigh……

-Mark

7. Mark Bobak says:

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

8. Franco says:

Thanks for this wonderful and amazing sql! It’s really impressive 🙂

9. Garry says:

It is sad that this site thinks Mac OS X Safari is “

10. Nik says:

you need to read this. This guy wrote a high-performance stored-procedure version of the same thing:

http://www.devx.com/dbzone/Article/33551

FULL DISCLOSURE: That guy happens to be my dad 😉

11. Mike Brandt says:

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=2define maxval=100set numwidth 6set pages 0set feedback offset verify offcolumn a3  format a3column a15 format a15column num format 9999promptprompt Solve the problem set by:promptprompt  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;promptprompt Paul: I don't know what the numbers areprompt Sam : I knew that. I don't know what the numbers are eitherpromptprompt Paul's first statement is more helpful than it first appearsprompt The pair of numbers cannot be uniquely determined by their productprompt 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 17prompt (assuming we are only looking at 2 digit numbers)promptprompt Sam's first statement is even more helpful.prompt Sam knows that Paul can't possibly know the numbersprompt So whatever his sum is, it cannot prompt be formed by a pair that uniquely determines their productprompt For example : the sum cannot be 18, or 57 or 94 using the above examplespromptprompt generate poss_sums as prompt the only sums that cannot possibly be made by distinct product pairsprompt There are surprisingly fewpause 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);promptprompt From Sam's first statement the sum must be one ofpromptselect s from poss_sumsorder by s;promptprompt Paul's last statement:prompt Paul: I do now!promptprompt So Paul knows that Sam knew that he did not know the numbers and so prompt must have a sum matching the above criterionprompt 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 listprompt 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 abovepromptpause Ready?create view poss_prods asselect products.p,max(poss_sums.s) s from products,pairs,poss_sumswhere products.cc &gt; 1  and pairs.a*pairs.b = products.p  and pairs.a+pairs.b = poss_sums.sgroup by products.phaving count(poss_sums.s) = 1;select 'product is ', p, 'sum is', s from poss_prodsorder 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 listprompt Otherwise Sam could still not deduce the pair.prompt and as we know both the product and the sum we can find the pairpromptpause Ready?col plan_plus_exp for a120set lines 160select 'In the range' a15,min(num) num,'to' a3,max(num) num from nums;set autotrace on explainselect 'The numbers are' a15, a num,'and' a3, b numfrom pairs,   ( select max(p) p,s from poss_prods group by s having count(*) = 1) ppwhere pairs.a*pairs.b = pp.p  and pairs.a+pairs.b= pp.sorder by a,b;set autotrace offdrop view poss_prods;drop view poss_sums;drop view products;drop view sums;drop view pairs;promptprompt or to be perverse, and use only in-line viewspause 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     )                                                          ppwhere pairs.a*pairs.b = pp.p  and pairs.a+pairs.b= pp.sorder by a,b;set autotrace offset timing offdrop table nums; `

12. Patrick Sinke says:

I lost you directly after the ‘select string from dual’ I’m afraid. I hope I never have to write anything like this 😉

13. nikola says:

respect!

14. Marco Gralike says:

As always; Brilliant.

15. grant czerepak says:

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.

## AMIS Technical Session: A closer look at Oracle Toplink (aka EclipseLink) - donderdag 7 juni, 18.00 uur

Oracle and Java are two of the main areas of our (at AMIS) expertise. They come together in many different ways, but particularly in Oracle Toplink. Peter Ebell, a long standing Toplink expert, formerly of Oracle Consulting’s Center of Excellence, now Expertise Manager at AMIS, takes us on a tour […] 