Weblog for the AMIS Technology corner
About the author : Anton Scheffer
No bio was found for this author yet...
More by Anton Scheffer
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 ' sfrom 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
5/6/2007 - 9:17 am
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.
5/6/2007 - 1:48 pm
As always; Brilliant.
5/6/2007 - 4:30 pm
respect!
5/6/2007 - 6:36 pm
I lost you directly after the ’select string from dual’ I’m afraid. I hope I never have to write anything like this
6/6/2007 - 6:40 pm
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).
9/6/2007 - 1:16 am
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/6/2007 - 5:03 am
It is sad that this site thinks Mac OS X Safari is “
12/6/2007 - 12:20 pm
Thanks for this wonderful and amazing sql! It’s really impressive
20/11/2007 - 6:04 pm
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
20/11/2007 - 6:08 pm
Never mind….just saw the comment about not working in 10.2.0.3…..sigh……
-Mark
21/11/2007 - 12:08 pm
At the end there’s a link named “code” to http://technology.amis.nl/blog/wp-content/images/sudomod.zip, the zip-file contains the SQL
13/8/2008 - 7:14 pm
Incroyable, très intéressant et challenge de résoudre une grille de Sudoku avec SQL, chapeau l’artiste.
18/2/2009 - 7:22 pm
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!
19/2/2009 - 9:37 am
My solver can solve any solvable sudoku.