Lists: | pgsql-general |
---|
From: | Merlin Moncure <mmoncure(at)gmail(dot)com> |
---|---|
To: | PostgreSQL General <pgsql-general(at)postgresql(dot)org> |
Subject: | sudoku in an sql statement |
Date: | 2009-10-31 13:32:14 |
Message-ID: | b42b73150910310632y29523c6esbc1faab2dc4a062@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
merlin
From: | Byran <sheepjxx(at)gmail(dot)com> |
---|---|
To: | Merlin Moncure <mmoncure(at)gmail(dot)com> |
Cc: | PostgreSQL General <pgsql-general(at)postgresql(dot)org> |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-10-31 23:17:04 |
Message-ID: | 37a11ce00910311617j76bc465bxca053c32d7f1e87e@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
From: | Thomas Kellerer <spam_eater(at)gmx(dot)net> |
---|---|
To: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-10-31 23:32:03 |
Message-ID: | hcihdj$k5s$1@ger.gmane.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | Thomas Kellerer <spam_eater(at)gmx(dot)net> |
Cc: | pgsql-general(at)postgresql(dot)org, Merlin Moncure <mmoncure(at)gmail(dot)com> |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-11-01 15:19:47 |
Message-ID: | 6273.1257088787@sss.pgh.pa.us |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
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
From: | Scott Marlowe <scott(dot)marlowe(at)gmail(dot)com> |
---|---|
To: | marcin mank <marcin(dot)mank(at)gmail(dot)com> |
Cc: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, 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:21:07 |
Message-ID: | dcc563d10911041521l464c25c4k26838d82da6b5f25@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
From: | Andrej <andrej(dot)groups(at)gmail(dot)com> |
---|---|
To: | marcin mank <marcin(dot)mank(at)gmail(dot)com> |
Cc: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, 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:21:30 |
Message-ID: | b35603930911041521p1a908095hd7ae6bd410b0bb1d@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
From: | Greg Stark <gsstark(at)mit(dot)edu> |
---|---|
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:28:20 |
Message-ID: | 407d949e0911041528x1c204ff4kbdfdd8059eb2f984@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Richard Broersma <richard(dot)broersma(at)gmail(dot)com> |
---|---|
To: | marcin mank <marcin(dot)mank(at)gmail(dot)com> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-11-04 23:31:09 |
Message-ID: | 396486430911041531r1596e2aek401766e7f55aabbb@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Andrej <andrej(dot)groups(at)gmail(dot)com> |
---|---|
To: | Richard Broersma <richard(dot)broersma(at)gmail(dot)com> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-11-04 23:38:04 |
Message-ID: | b35603930911041538y705bda73j3ca57583c0ca770a@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
From: | marcin mank <marcin(dot)mank(at)gmail(dot)com> |
---|---|
To: | Richard Broersma <richard(dot)broersma(at)gmail(dot)com> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-11-04 23:39:52 |
Message-ID: | b1b9fac60911041539g36b78b38v57652337544993f3@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | marcin mank <marcin(dot)mank(at)gmail(dot)com> |
---|---|
To: | Richard Broersma <richard(dot)broersma(at)gmail(dot)com> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-11-04 23:59:25 |
Message-ID: | b1b9fac60911041559s4ff5c10av2ffa00b60723c4e5@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Hitoshi Harada <umi(dot)tanuki(at)gmail(dot)com> |
---|---|
To: | marcin mank <marcin(dot)mank(at)gmail(dot)com> |
Cc: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, 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-05 07:33:07 |
Message-ID: | e08cc0400911042333o5361b21cu2c9438f82b1e55ce@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Thomas Kellerer <spam_eater(at)gmx(dot)net> |
---|---|
To: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: sudoku in an sql statement |
Date: | 2009-11-05 17:38:22 |
Message-ID: | hcv2ie$blj$1@ger.gmane.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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