Re: sudoku in an sql statement

an oracle guy wrote an sql statement that solves a sudoku
puzzle...using an oracle specific feature. Still, it's pretty neat,
and an absolute gem of lateral thinking.

http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring

merlin

Really brilliant.

2009/11/1 Merlin Moncure <mmoncure(at)gmail(dot)com>

> an oracle guy wrote an sql statement that solves a sudoku
> puzzle...using an oracle specific feature. Still, it's pretty neat,
> and an absolute gem of lateral thinking.
>
>
> http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring
>
> merlin
>
> --
> Sent via pgsql-general mailing list (pgsql-general(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-general
>

--
Interest in every thing in database.

Merlin Moncure wrote on 31.10.2009 14:32:
> an oracle guy wrote an sql statement that solves a sudoku
> puzzle...using an oracle specific feature. Still, it's pretty neat,
> and an absolute gem of lateral thinking.
>
> http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring
>
> merlin
>
There is also a DB2 version:
http://forums.devshed.com/db2-development-114/absolute-sudoku-solver-641065.html

That guy also wrote a statement to select prime numbers:
http://forums.devshed.com/db2-development-114/prime-numbers-in-plain-db2t-640347.html

and to solve equations:
http://forums.devshed.com/db2-development-114/equation-solver-plain-db2t-643752.html

Thomas Kellerer <spam_eater(at)gmx(dot)net> writes:
> Merlin Moncure wrote on 31.10.2009 14:32:
>> an oracle guy wrote an sql statement that solves a sudoku
>> puzzle...using an oracle specific feature. Still, it's pretty neat,
>> and an absolute gem of lateral thinking.
>>
>> http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring

> There is also a DB2 version:
> http://forums.devshed.com/db2-development-114/absolute-sudoku-solver-641065.html

The DB2 version looks amazingly brute-force :-(

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.
Don't have time to try it myself right now, though.

regards, tom lane

> 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

This needs to be published...

On Wed, Nov 4, 2009 at 4:18 PM, marcin mank <marcin(dot)mank(at)gmail(dot)com> wrote:
>> 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
>
> --
> Sent via pgsql-general mailing list (pgsql-general(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-general
>

--
When fascism comes to America, it will be intolerance sold as diversity.

2009/11/5 marcin mank <marcin(dot)mank(at)gmail(dot)com>:

> btw2: is SQL with 'with recursive' turing-complete ? Anyone care to
> try a Brainf*ck interpreter ? :)
Sick, sick puppy! :}

Cheers,
Andrej

--
Please don't top post, and don't use HTML e-Mail :} Make your quotes concise.

http://www.american.edu/econ/notes/htmlmail.htm

On Sun, Nov 1, 2009 at 3:19 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> 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.
> Don't have time to try it myself right now, though.

Interestingly the first thing I ran into when I started doing so was
that apparently Oracle *doesn't* handle the lack of the RECURSIVE
attribute properly. It still put the common table expressions in scope
for the subsequent common table expressions even without the RECURSIVE
keyword, which is apparently just a noise word in Oracle.

--
greg

On Wed, Nov 4, 2009 at 3:18 PM, marcin mank <marcin(dot)mank(at)gmail(dot)com> wrote:

>                                         s
> -----------------------------------------------------------------------------------
>  534678912672195348198342567859761423426853791713924856961537284287419635345286179
> (1 row)

I don't get the same results:

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

--
Regards,
Richard Broersma Jr.

Visit the Los Angeles PostgreSQL Users Group (LAPUG)
http://pugs.postgresql.org/lapug

2009/11/5 Richard Broersma <richard(dot)broersma(at)gmail(dot)com>:
> On Wed, Nov 4, 2009 at 3:18 PM, marcin mank <marcin(dot)mank(at)gmail(dot)com> wrote:
>> -----------------------------------------------------------------------------------
>> 534678912672195348198342567859761423426853791713924856961537284287419635345286179
>> (1 row)

> broersr=> with recursive x( s, ind ) as
> broersr-> ( select sud, position( ' ' in sud )
> broersr(> from (select '53 7 6 195 98 6 8 6 34 8 3 17 2
> broersr'> 6 6 28 419 5 8 79'::text as sud) xx

Get rid of that line-wrap - it screwed up the spacing.

> broersr(> union all
> broersr(> select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
> broersr(> , position(' ' in repeat('x',ind) || substr( s, ind + 1 ) )
> broersr(> from x
> broersr(> , (select gs::text as z from generate_series(1,9) gs)z
> broersr(> where ind > 0
> broersr(> and not exists ( select null
> broersr(> from generate_series(1,9) lp
> broersr(> where z.z = substr( s, ( (ind - 1 ) / 9 )
> * 9 + lp, 1 )
> broersr(> or z.z = substr( s, mod( ind - 1, 9 ) -
> 8 + lp * 9, 1 )
> broersr(> or z.z = substr( s, mod( ( ( ind - 1 )
> / 3 ), 3 ) * 3
> broersr(> + ( ( ind - 1 ) / 27 ) * 27 + lp
> broersr(> + ( ( lp - 1 ) / 3 ) * 6
> broersr(> , 1 )
> broersr(> )
> broersr(> )
> broersr-> select s
> broersr-> from x
> broersr-> where ind = 0;
> s
> ---
> (0 rows)

Cheers,
Andrej

--
Please don't top post, and don't use HTML e-Mail :} Make your quotes concise.

http://www.american.edu/econ/notes/htmlmail.htm

On Thu, Nov 5, 2009 at 12:31 AM, Richard Broersma
<richard(dot)broersma(at)gmail(dot)com> wrote:
> I don't get the same results:

This is due to my email client breaking the lines.
Try this: http://pastebin.com/f2a0884a1

Greetings
Marcin Mańk

On Thu, Nov 5, 2009 at 12:39 AM, marcin mank <marcin(dot)mank(at)gmail(dot)com> wrote:
> On Thu, Nov 5, 2009 at 12:31 AM, Richard Broersma
> <richard(dot)broersma(at)gmail(dot)com> wrote:
>> I don't get the same results:
>
> This is due to my email client breaking the lines.
> Try this: http://pastebin.com/f2a0884a1

doh.
http://www.pastie.org/684163

Greetings
Marcin Mańk

2009/11/5 marcin mank <marcin(dot)mank(at)gmail(dot)com>:
>> 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)
>
I'd prefer the output be with question and formatted :)

SELECT regexp_replace(regexp_split_to_table(regexp_replace(s,
'.{9}(?!$)', '\\&-', 'g'), '-'), '.{3}(?!$)', '\\&|', 'g') AS answer
,regexp_replace(regexp_split_to_table(regexp_replace(org, '.{9}(?!$)',
'\\&-', 'g'), '-'), '.{3}(?!$)', '\\&|', 'g') AS question
FROM(
SELECT
*, first_value(s) OVER () AS org
FROM
x
)x
WHERE position(' ' in s) = 0;
answer | question
-------------+-------------
534|678|912 | 53 | 7 |
672|195|348 | 6 |195|
198|342|567 | 98| | 6
859|761|423 | 8 | 6 | 3
426|853|791 | 4 |8 3| 1
713|924|856 | 7 | 2 | 6
961|537|284 | 6 | |28
287|419|635 | |419| 5
345|286|179 | | 8 | 79
(9 rows)

Regards,

--
Hitoshi Harada

Greg Stark wrote on 05.11.2009 00:28:
> Interestingly the first thing I ran into when I started doing so was
> that apparently Oracle *doesn't* handle the lack of the RECURSIVE
> attribute properly. It still put the common table expressions in scope
> for the subsequent common table expressions even without the RECURSIVE
> keyword, which is apparently just a noise word in Oracle.

It is a "noise" word in Oracle, DB2 and SQL Server.

Only Postgres and Firebird completely adhere to the standard by requiring it...

Thomas