a "dancing links" sudoku algorithm implemented in "pure" sql

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