# 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[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:,

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