Skip site navigation (1) Skip section navigation (2)

Re: sudoku in an sql statement

From: marcin mank <marcin(dot)mank(at)gmail(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Thomas Kellerer <spam_eater(at)gmx(dot)net>, pgsql-general(at)postgresql(dot)org, Merlin Moncure <mmoncure(at)gmail(dot)com>
Subject: Re: sudoku in an sql statement
Date: 2009-11-04 23:18:26
Message-ID: b1b9fac60911041518o3c5f6917r9d47b60feab76512@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-general
> I think the Oracle guy's version could easily be adapted to PG 8.4 ---
> those little rownum subqueries seem to be just a substitute for not
> having generate_series(1,9), and everything else is just string-pushing.

indeed.

marcin=# with recursive x( s, ind ) as
( select sud, position( ' ' in sud )
  from  (select '53  7    6  195    98    6 8   6   34  8 3  17   2
6 6    28    419  5    8  79'::text as sud) xx
  union all
  select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , position(' ' in repeat('x',ind) || substr( s, ind + 1 ) )
  from x
     ,  (select gs::text as z from generate_series(1,9) gs)z
  where ind > 0
  and not exists ( select null
                   from generate_series(1,9) lp
                   where z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 + lp, 1 )
                   or    z.z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   or    z.z = substr( s, mod( ( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + ( ( ind - 1 ) / 27 ) * 27 + lp
                                      + ( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
select s
from x
where ind = 0;
                                         s
-----------------------------------------------------------------------------------
 534678912672195348198342567859761423426853791713924856961537284287419635345286179
(1 row)

Time: 472.027 ms


btw: it is pretty cool to replace some of the numbers in input with
spaces and see how the query finds multiple solutions

btw2: is SQL with 'with recursive' turing-complete ? Anyone care to
try a Brainf*ck interpreter ? :)

Greetings
marcin Mańk

In response to

Responses

pgsql-general by date

Next:From: Scott MarloweDate: 2009-11-04 23:21:07
Subject: Re: sudoku in an sql statement
Previous:From: John R PierceDate: 2009-11-04 23:06:23
Subject: Re: Where I can find "SSL specification"?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group