-- Weekend practice : 2012-09-30
--
-- having recently discovered the Common Table Expressions, I wanted to see
if the SQL powerfull (threaded) motors
-- could run sophisticated algorithms (not "brute force") more quickly than
classic langages.
--
-- result : "could" = yes, "more quickly" = no, but I'm a postgresql
beginner level and it is a vintage hardware
--
-- Does anyone has ideas to make the "dancing link" algorithm performant
than the "brute" force ?
--
-- Do you have more favorable results for "dancing links" on your bigger
hardware, compared to "brute" force ?
--
-- ======================================================================
-- implementing the dancing link algorithm in pure sql to solve a sudoku
-- unfortunately : "dancing links" analyze 2067 possibilities only, but in
55 seconds
-- brute force is quicker : 18885 possibilities in 8 seconds
-- in python on same machine (centrino first generation, year 2003) , it's
3 seconds
-- ======================================================================
CREATE OR REPLACE FUNCTION whites(f text)
-- gives the table with the empty columns numbers
RETURNS SETOF integer
LANGUAGE SQL
AS $$
select gs FROM generate_series(1,length($1)) gs where substr( $1, gs, 1
)=' ' ;
$$;
CREATE OR REPLACE function possibles(s text, ind integer)
-- gives the table of possible pieces to put in given "ind" position of the
current "s" sudoku problem
RETURNS SETOF text
LANGUAGE SQL
AS $$
select z from (SELECT gs::text AS z FROM generate_series(1,9) gs) z
WHERE NOT EXISTS ( SELECT NULL
FROM generate_series(1,9) lp
WHERE z = substr( $1, ( ($2 - 1 ) / 9 ) * 9 + lp, 1 )
OR z = substr( $1, mod( $2 - 1, 9 ) - 8 + lp * 9, 1 )
OR z = substr( $1, mod( ( ( $2 - 1 ) / 3 ), 3 ) * 3
+ ( ( $2 - 1 ) / 27 ) * 27 + lp
+ ( ( lp - 1 ) / 3 ) * 6
, 1 )
)
$$;
CREATE OR REPLACE function recommands2(s text , holes integer)
-- gives the least possible positions to evaluate from initial "s" sudoku
-- if the initial "s" sudoku is discovered non-solvable, there is no output
RETURNS SETOF text
LANGUAGE SQL
AS $$
with
-- search the smallest group of solutions to try from initial "s" sudoku
moves(posit, pion, nb, nblg , nbco, nbsq, line, colo, square) as(
select dd, pp, least(score, nblg , nbco, nbsq) as nb, nblg ,
nbco, nbsq, line , colo, square from (
select dd, pp , sum(100000 + dd ) over (partition by dd) as score,
sum(110000+100*line+dd) over (partition by line, dd) as
nblg ,
sum(120000+100*colo+dd) over (partition by colo, dd) as
nbco,
sum(130000+100*square+dd) over (partition by square, dd)
as nbsq ,
line, colo, square from (select d as dd , possibles($1, d) as pp,
(d-1)/9 as line,
mod(d-1 , 9) as colo ,
mod( ( ( d - 1 ) / 3 ), 3 ) * 3 + ( ( d - 1 ) / 27 ) as square from
(
select whites($1) as d ) as ee
) tyty) dsgf) ,
-- we must be able to play all empty position of the initial "s" sudoku
given
unfounds(nb_nosol, nbmin) as (
select $2 - count(*) , min(nb) from (
select distinct posit , nb from moves) as meme ) ,
-- we must be able to play as much different pieces in any given column,
line, sub-square
-- as there are empty holes in these sub-parts of the of the initial "s"
sudoku given
-- (as you can't play "more", a global check is sufficient, I suppose)
unfound_lines(issues) as (
select 3*$2 - sum(1) as issues from (select distinct pion r, line
t from moves
union all select distinct pion r, colo t from moves
union all select distinct pion r, square t from moves
) dfdf )
-- gives minimal group of solutions to try, is current "s" sudoku is still
a possible solution
select substr( $1, 1, a.posit - 1 ) || a.pion || substr( $1, a.posit + 1 )
from
moves as a, unfounds, unfound_lines where a.nb=nbmin and nb_nosol=0 and
issues=0
$$;
WITH RECURSIVE
--'53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419
5 8 79' 2sec
--
-- 184 sec with dancing link vs 9 without
--'1 7 9 3 2 8 96 5 53 9 1 8 26 4 3 1 4
7 7 3 '
--'111111111222222222333333333444444444555555555666666666777777777888888888999999999'
sudoku(initial) as (select (
'1 7 9 3 2 8 96 5 53 9 1 8 26 4 3 1 4 7
7 3 '::text)),
x( s, ind ) AS
( SELECT initial, length(initial) -length(replace(initial, ' ', '') )
FROM sudoku
UNION ALL
(with
reco(s, ind, posi) as (select x.s , x.ind, recommands(x.s) from x where
ind>0)
SELECT substr( s, 1, posi - 1 ) || possibles(s, posi) || substr( s, posi
+ 1 )
, ind-1
FROM reco
)
),
q( s, ind ) AS
( SELECT initial, length(initial) -length(replace(initial, ' ', '') )
FROM sudoku
UNION ALL
SELECT recommands2(q.s, q.ind) , q.ind-1 FROM q where ind>0
)
SELECT * FROM q WHERE ind >= 0 order by ind -- 0= sudoku, >=0 to show all
possibilities evaluated
-- "brute force" algorithm is :
http://archives.postgresql.org/pgsql-general/2009-11/msg00150.php
