sudoku in an sql statement
|
View:
New views
14 Messages
—
Rating Filter:
Alert me
|
 |
sudoku in an sql statement
by Merlin Moncure-2
::
Rate this Message:
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@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Byran-2
::
Rate this Message:
Really brilliant.
2009/11/1 Merlin Moncure <mmoncure@...> an oracle guy wrote an sql statement that solves a sudoku -- Interest in every thing in database. |
|
|
Re: sudoku in an sql statement
by Thomas Kellerer
::
Rate this Message:
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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Tom Lane-2
::
Rate this Message:
Thomas Kellerer <spam_eater@...> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Marcin Mank-2
::
Rate this Message:
> 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@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Scott Marlowe-2
::
Rate this Message:
This needs to be published...
On Wed, Nov 4, 2009 at 4:18 PM, marcin mank <marcin.mank@...> 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@...) > 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. -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Andrej Ricnik-Bay
::
Rate this Message:
2009/11/5 marcin mank <marcin.mank@...>:
> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Greg Stark-5
::
Rate this Message:
On Sun, Nov 1, 2009 at 3:19 PM, Tom Lane <tgl@...> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Richard Broersma
::
Rate this Message:
On Wed, Nov 4, 2009 at 3:18 PM, marcin mank <marcin.mank@...> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Andrej Ricnik-Bay
::
Rate this Message:
2009/11/5 Richard Broersma <richard.broersma@...>:
> On Wed, Nov 4, 2009 at 3:18 PM, marcin mank <marcin.mank@...> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Marcin Mank-2
::
Rate this Message:
On Thu, Nov 5, 2009 at 12:31 AM, Richard Broersma
<richard.broersma@...> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Marcin Mank-2
::
Rate this Message:
On Thu, Nov 5, 2009 at 12:39 AM, marcin mank <marcin.mank@...> wrote:
> On Thu, Nov 5, 2009 at 12:31 AM, Richard Broersma > <richard.broersma@...> 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Hitoshi Harada-2
::
Rate this Message:
2009/11/5 marcin mank <marcin.mank@...>:
>> 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) > 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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
|
|
Re: sudoku in an sql statement
by Thomas Kellerer
::
Rate this Message:
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 -- Sent via pgsql-general mailing list (pgsql-general@...) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general |
| Free embeddable forum powered by Nabble | Forum Help |
