sodoku, or... now we can do everything in stored procedures!

[Arjen Lentz]

Stored Procedures are a useful -but much abused- feature. Why abused? Well, sometimes it just doesn't make any sense to put certain functionality into the database server.

A key positive is that business logic can be handled and enforced inside your RDBMS. Good! But something to also consider in the real world is the fact that you generally have more web or application servers than database servers. So for scaling, loading the database servers more can be an inefficient use of resources. It can make more sense to spread such tasks across the web/app servers. Of course it's not a black & white story. Like any other tool, it has its positives and drawbacks.

So, about doing weird things in SQL... Per-Erik Martin, the MySQL developer who led the implementation of stored procedures in MySQL 5.0, has written the following. It's an SQL implementation of a <a href="http://www.sudoku.com/">sodoku</a>; puzzle solver. Senseless, certainly ;-) but it can still be interesting to look at these things as examples of what is possible with SQL. Per-Erik's own excuse:

"A complete compile-pentium-valgrind-max build takes about 45 minutes on my not-too-fast machine, and the test run about 35 minutes. It's not always possible to fill this time with something useful to do, so it can get a little boring at times..."

--
-- The SQL Sudoku Solver
--
-- It's basically a backtracking generate-and-test solver, i.e. "brute force",
-- but with a scheduler that increases the chance to find conflicts as soon
-- as possible.
--
-- Written by Per-Erik Martin
--
-- (It's actually a fairly straighforward translation of a C program by the
-- same author. The C program solves any sudoku puzzle in less than 1 second
-- on an average 1GHz+ computer.
-- I don't claim that this is the best way to do it in SQL, nor that it's
-- a good idea to do it in SQL in the first place. I just thought it was a
-- cool thing to do. :)
--
--
-- Usage:
-- 1) Initialize the table 'sudoku' as shown in the examples below,
-- e.g. call easy_sudoku();
-- 2) call sudoku_solve(false, false);
--
-- A result set with the solution is returned, along with the number
-- of tests done. (This gives some measurement of how difficult the
-- puzzle is.)
-- The table 'sudoku' is not modified.
-- (See below for more explanations of the parameters.)
--

-- The input: An "array" of the sudoku puzzle, null for empty slots.
drop table if exists sudoku;
create table sudoku
(
idx int not null auto_increment primary key,
dig smallint
);


----------------------------------------------------------------------------
--
-- For convenience, a few procedures to initialize the sudoku table for
-- some test cases.
--

-- Easy - takes a few seconds to solve
-- 726 483 951
-- 149 275 638
-- 385 916 472
--
-- 862 359 147
-- 534 721 869
-- 971 864 523
--
-- 453 192 786
-- 617 538 294
-- 298 647 315
drop procedure if exists easy_sudoku;
delimiter //
create procedure easy_sudoku()
deterministic
modifies sql data
begin
delete from sudoku;
insert into sudoku (dig) values
(null),(null),(null), (null),(null),( 3 ), (null),( 5 ),( 1 ),
( 1 ),( 4 ),(null), (null),( 7 ),(null), ( 6 ),(null),(null),
(null),( 8 ),( 5 ), ( 9 ),(null),(null), ( 4 ),(null),( 2 ),

(null),(null),( 2 ), ( 3 ),(null),(null), ( 1 ),(null),( 7 ),
( 5 ),( 3 ),(null), (null),(null),(null), (null),( 6 ),(null),
( 9 ),(null),(null), ( 8 ),( 6 ),( 4 ), (null),( 2 ),(null),

(null),( 5 ),(null), ( 1 ),(null),( 2 ), (null),( 8 ),(null),
( 6 ),(null),( 7 ), ( 5 ),(null),(null), (null),( 9 ),(null),
(null),(null),(null), (null),(null),( 7 ), ( 3 ),( 1 ),(null);
end//
delimiter ;

-- Hard - takes a few minutes to solve
-- 143 986 257
-- 679 425 381
-- 285 731 694
--
-- 962 354 178
-- 357 618 942
-- 418 279 563
--
-- 821 567 439
-- 796 143 825
-- 534 892 716
drop procedure if exists hard_sudoku;
delimiter //
create procedure hard_sudoku()
deterministic
modifies sql data
begin
delete from sudoku;
insert into sudoku (dig) values
(null),( 4 ),( 3 ), (null),( 8 ),(null), ( 2 ),( 5 ),(null),
( 6 ),(null),(null), (null),(null),(null), (null),(null),(null),
(null),(null),(null), (null),(null),( 1 ), (null),( 9 ),( 4 ),

( 9 ),(null),(null), (null),(null),( 4 ), (null),( 7 ),(null),
(null),(null),(null), ( 6 ),(null),( 8 ), (null),(null),(null),
(null),( 1 ),(null), ( 2 ),(null),(null), (null),(null),( 3 ),

( 8 ),( 2 ),(null), ( 5 ),(null),(null), (null),(null),(null),
(null),(null),(null), (null),(null),(null), (null),(null),( 5 ),
(null),( 3 ),( 4 ), (null),( 9 ),(null), ( 7 ),( 1 ),(null);
end//
delimiter ;

-- Faulty - fails within seconds
drop procedure if exists fail_sudoku;
delimiter //
create procedure fail_sudoku()
deterministic
modifies sql data
begin
delete from sudoku;
insert into sudoku (dig) values
(null),(null),(null), (null),(null),( 3 ), (null),( 5 ),( 1 ),
( 1 ),( 4 ),(null), (null),( 7 ),(null), ( 6 ),(null),(null),
(null),( 8 ),( 5 ), ( 1 ),(null),(null), ( 4 ),(null),( 2 ),

(null),(null),( 2 ), ( 3 ),(null),(null), ( 1 ),(null),( 7 ),
( 5 ),( 3 ),(null), (null),(null),(null), (null),( 6 ),(null),
( 9 ),(null),(null), ( 8 ),( 6 ),( 4 ), (null),( 2 ),(null),

(null),( 5 ),(null), ( 1 ),(null),( 2 ), (null),( 8 ),(null),
( 6 ),(null),( 7 ), ( 5 ),(null),(null), (null),( 9 ),(null),
(null),(null),(null), (null),(null),( 7 ), ( 3 ),( 1 ),(null);
end//
delimiter ;

-- Ambiguous - beware, this takes a very long time to run...
drop procedure if exists ambig_sudoku;
delimiter //
create procedure ambig_sudoku()
deterministic
modifies sql data
begin
delete from sudoku;
insert into sudoku (dig) values
(null),( 4 ),( 3 ), (null),( 8 ),(null), ( 2 ),( 5 ),(null),
( 6 ),(null),(null), (null),(null),(null), (null),(null),(null),
(null),(null),(null), (null),(null),( 1 ), (null),( 9 ),( 4 ),

( 9 ),(null),(null), (null),(null),( 4 ), (null),( 7 ),(null),
(null),(null),(null), ( 6 ),(null),( 8 ), (null),(null),(null),
(null),( 1 ),(null), ( 2 ),(null),(null), (null),(null),( 3 ),

(null),( 2 ),(null), ( 5 ),(null),(null), (null),(null),(null),
(null),(null),(null), (null),(null),(null), (null),(null),( 5 ),
(null),( 3 ),( 4 ), (null),( 9 ),(null), ( 7 ),( 1 ),(null);
end//
delimiter ;


----------------------------------------------------------------------------
--
-- The solver
--

-- Normal usage: call sudoku_solve(false, false);
--
-- If the first parameter is 'true', the slots are tried in some arbitrary
-- order.
-- If it's 'false', a "clever" schedule is used which usually solves it a
-- lot faster.
--
-- If the second parameter is 'true', it attempts to find all possible
-- solutions. (A correct puzzle should only have one solution of course.)
-- If it's 'false', it stops when the first solution is found.
--
drop procedure if exists sudoku_solve;
delimiter //
create procedure sudoku_solve(p_naive boolean, p_all boolean)
deterministic
modifies sql data
begin
drop temporary table if exists sudoku_work, sudoku_schedule;

create temporary table sudoku_work
(
row smallint not null,
col smallint not null,
dig smallint not null,
cnt smallint,
key(row),
key(col),
unique key(row,col)
);

create temporary table sudoku_schedule
(
idx int not null auto_increment primary key,
row smallint not null,
col smallint not null
);

call sudoku_init();

if p_naive then
update sudoku_work set cnt = 0 where dig = 0;
else
call sudoku_count();
end if;
insert into sudoku_schedule (row,col)
select row,col from sudoku_work where cnt is not null order by cnt desc;

begin
declare v_tcounter bigint default 0;
declare v_scounter bigint default 0;
declare v_i smallint default 1;
declare v_dig smallint;
declare v_schedmax smallint;

select count(*) into v_schedmax from sudoku_schedule;

more: loop
sched: while v_i <= v_schedmax do
begin
declare v_row, v_col smallint;

select row,col into v_row,v_col from sudoku_schedule where v_i = idx;

select dig into v_dig from sudoku_work
where v_row = row and v_col = col;

case v_dig
when 0 then
set v_dig = 1;
update sudoku_work set dig = 1
where v_row = row and v_col = col;
when 9 then
if v_i > 0 then
update sudoku_work set dig = 0
where v_row = row and v_col = col;
set v_i = v_i - 1;
iterate sched;
else
select v_scounter as 'Solutions';
leave more;
end if;
else
set v_dig = v_dig + 1;
update sudoku_work set dig = v_dig
where v_row = row and v_col = col;
end case;

set v_tcounter = v_tcounter + 1;
if not sudoku_digit_ok(v_row, v_col, v_dig) then
iterate sched;
end if;
set v_i = v_i + 1;
end;
end while sched;

select dig from sudoku_work;
select v_tcounter as 'Tests';
set v_scounter = v_scounter + 1;

if p_all and v_i > 0 then
set v_i = v_i - 1;
else
leave more;
end if;
end loop more;
end;

drop temporary table sudoku_work, sudoku_schedule;
end//
delimiter ;

-- Initialize the sudoku_work table from the input (sudoku) table.
--
drop procedure if exists sudoku_init;
delimiter //
create procedure sudoku_init()
deterministic
modifies sql data
begin
declare v_row, v_col smallint;
declare c cursor for select dig from sudoku order by idx;
declare exit handler for not found close c;

set v_row = 0, v_col = 0;
open c;
loop
begin
declare v_dig smallint;

fetch c into v_dig;
if isnull(v_dig) then
set v_dig = 0;
end if;
insert into sudoku_work (row,col,dig) values (v_row, v_col, v_dig);
if v_col < 8 then
set v_col = v_col + 1;
else
set v_col = 0;
set v_row = v_row + 1;
end if;
end;
end loop;
end//
delimiter ;

-- Update the sudoku_work table with the inference counters - i.e. the
-- number of preset values that affects the choice of value for each empty
-- slot.
--
drop procedure if exists sudoku_count;
delimiter //
create procedure sudoku_count()
deterministic
modifies sql data
begin
declare c cursor for select row,col,dig from sudoku_work where dig = 0;
declare exit handler for not found close c;

open c;
loop
begin
declare v_row, v_col, v_dig, v_count smallint;
declare v_cell_row_low, v_cell_row_high smallint;
declare v_cell_col_low, v_cell_col_high smallint;

fetch c into v_row, v_col, v_dig;
set v_cell_row_low = v_row - (v_row % 3);
set v_cell_row_high = v_cell_row_low + 3;
set v_cell_col_low = v_col - (v_col % 3);
set v_cell_col_high = v_cell_col_low + 3;

select count(*) into v_count
from sudoku_work
where dig > 0 and
((row = v_row and col != v_col) or
(row != v_row and col = v_col) or
(row != v_row and col != v_col and
v_cell_row_low <= row and row < v_cell_row_high and
v_cell_col_low <= col and col < v_cell_col_high));

update sudoku_work set cnt = v_count
where row = v_row and col = v_col;

end;
end loop;
end//
delimiter ;

-- Check if it's ok to put a digit in a given slot.
--
drop function if exists sudoku_digit_ok;
delimiter //
create function sudoku_digit_ok(p_row smallint, p_col smallint, p_val smallint)
returns boolean
deterministic
reads sql data
begin
declare v_count smallint;
declare v_cell_row_low, v_cell_row_high smallint;
declare v_cell_col_low, v_cell_col_high smallint;

set v_cell_row_low = p_row - (p_row % 3);
set v_cell_row_high = v_cell_row_low + 3;
set v_cell_col_low = p_col - (p_col % 3);
set v_cell_col_high = v_cell_col_low + 3;

select count(*) into v_count from sudoku_work
where dig = p_val and
row = p_row and col != p_col;
if v_count > 0 then
return false;
end if;
select count(*) into v_count from sudoku_work
where dig = p_val and
row != p_row and col = p_col;
if v_count > 0 then
return false;
end if;
select count(*) into v_count from sudoku_work
where dig = p_val and
row != p_row and col != p_col and
v_cell_row_low <= row and row < v_cell_row_high and
v_cell_col_low <= col and col < v_cell_col_high;
return v_count = 0;
end//
delimiter ;

Regards, Arjen.
--
Arjen Lentz, Exec.Director @ Open Query (http://openquery.com)
Remote expertise & maintenance for MySQL/MariaDB server environments.

Follow us at http://openquery.com/blog/ & http://twitter.com/openquery