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.
merlin
Really brilliant.
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.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.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.
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 solutionsbtw2: 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.
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.
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