Thread: 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.
--
Interest in every thing in database.
2009/11/1 Merlin Moncure <mmoncure@gmail.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@postgresql.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@gmx.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.mank@gmail.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@postgresql.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.mank@gmail.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@sss.pgh.pa.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.mank@gmail.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.broersma@gmail.com>:
> On Wed, Nov 4, 2009 at 3:18 PM, marcin mank <marcin.mank@gmail.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.broersma@gmail.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.mank@gmail.com> wrote: > On Thu, Nov 5, 2009 at 12:31 AM, Richard Broersma > <richard.broersma@gmail.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.mank@gmail.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