Archives for category: SQL

Cool:

Juozas solves sudokus in a readble mysql query.

And for a mental break after a few weeks of living swamped-in-code, here’s One Tough Puzzle.

I spent a good deal of time writing programs to solve puzzles – in Java and PROLOG – for my AI Bachelor’s, and the last several solving problems that are harder and more useful to solve – in php and SQL. So it’s come to this, I’m using today’s tools to solve yesterday’s non-problems.

Here’s a hard-coded SQL script to solve this puzzle. It’s not terrifically extensible beyond 9 glossy pieces, but it is proof that SQL can do it given the chance.

CREATE TABLE tiles (id serial, one text, two text, three text, four text);

INSERT INTO tiles (one, two, three, four) VALUES

(‘s’,’s’,’h’,’c’),
(‘h’,’d’,’d’,’h’),
(‘s’,’d’,’h’,’d’),
(‘s’,’d’,’s’,’h’),
(‘c’,’h’,’d’,’c’),
(‘h’,’d’,’c’,’c’),
(‘h’,’s’,’s’,’c’),
(‘d’,’c’,’c’,’d’),
(‘c’,’h’,’s’,’h’);

SELECT mi.id as middle,
e1.id as cw1,
d1.id as cw2,
e2.id as cw3,
d2.id as cw4,
e3.id as cw5,
d3.id as cw6,
e4.id as cw7,
d4.id as cw8

FROM tiles AS mi

JOIN tiles AS e1 ON e1.id not in (mi.id) AND ((mi.one = e1.three) OR (mi.one = e1.four))
JOIN tiles AS e2 ON e2.id not in (mi.id, e1.id) AND ((mi.two = e2.three) OR (mi.two = e2.four))
JOIN tiles AS e3 ON e3.id not in (mi.id, e1.id, e2.id) AND ((mi.three = e3.one) OR (mi.three = e3.two))
JOIN tiles AS e4 ON e4.id not in (mi.id, e1.id, e2.id, e3.id) AND ((mi.four = e4.one) OR (mi.four = e4.two))

JOIN tiles AS d1 ON d1.id not in (mi.id, e1.id, e2.id, e3.id, e4.id) AND
(((e1.three = d1.one) AND (d1.four = e2.one)) OR
((e1.three = d1.two) AND (d1.one = e2.four)) OR
((e1.two = d1.three) AND (d1.two = e2.four)) OR
((e1.two = d1.four) AND (d1.three = e2.one)))

JOIN tiles AS d2 ON d2.id not in (mi.id, e1.id, e2.id, e3.id, e4.id, d1.id) AND
(((e2.three = d2.one) AND (d2.four = e3.two)) OR
((e2.three = d2.two) AND (d2.one = e3.three)) OR
((e2.two = d2.three) AND (d2.two = e3.three)) OR
((e2.two = d2.four) AND (d2.three = e3.two)))

JOIN tiles AS d3 ON d3.id not in (mi.id, e1.id, e2.id, e3.id, e4.id, d1.id, d2.id) AND
(((e3.four = d3.one) AND (d3.four = e4.two)) OR
((e3.four = d3.two) AND (d3.one = e4.three)) OR
((e3.one = d3.three) AND (d3.two = e4.three)) OR
((e3.one = d3.four) AND (d3.three = e4.two)))

JOIN tiles AS d4 ON d4.id not in (mi.id, e1.id, e2.id, e3.id, e4.id, d1.id, d2.id, d3.id) AND
(((e4.four = d4.one) AND (d4.four = e1.one)) OR
((e4.four = d4.two) AND (d4.one = e1.four)) OR
((e4.one = d4.three) AND (d4.two = e1.four)) OR
((e4.one = d4.four) AND (d4.three = e1.one)))

ORDER BY middle DESC;

The Art of SQL
By St├ęphane Faroult, Peter Robson

As we know, there are known knowns. There are things we know we know. We also know there are known unknowns. That is to say we know there are some things we do not know. But there are also unknown unknowns, the ones we don’t know we don’t know. – Donald Rumsfeld (Sun Tzu’s second millennium CE incarnation.)

The Art of SQL is no Web Database Applications with PHP and MySQL. It’s far beyond that; it is well past even Practical PostgreSQL and the SQL Cookbook. Not only is it written for the experienced user, it is for the ambitious user, the one who wakes up with a smile trying to retain the n-dimensional join from their dream.

The excellent style of writing used is above O’Reilly par. Not only is the text concise and well edited, the book is organized very well. In a graceful and creative turn, the presentational style of the book is allusive to Sun Tzu’s Art of War; query diagrams, sample datasets, and business cases are rendered as plans of attack and battle formations in the Napoleonic era. The result is phenomenal, and structurally, this book is groundbreaking – no computer science book I’ve read prior has had so much attention paid to making its content engaging and enjoyable to consume – this is certainly not necessary, but it is a great indication of the overall quality of the book.

The book is SQL implementation agnostic and assumes the reader is interested in data integrity, extensibility, and scalability in the database. It assumes that you care, or want to care, whether you’re following third normal form. In fact, the implied understanding here is that an earnest investment in normalization will pay dividends in optimization. Only if you’re willing to perspire for it – it is an art, not a school of magic.

The SQL enthusiast will learn a lot from this book – perhaps a baffling amount. I absolutely cannot recommend it highly enough. It has been some time coming, the sort of thing that is an obvious boon when one considers that our ‘art’ has only been around for a few decades. We’ll get it right eventually, inspired by those like Faroult and Robson.

I told my co-workers last week that SQL could help one figure out, among other puzzles, Eight Queens. I’m sure they believed me, but I couldn’t find it on the internets so I wrote it. Here it is, just run it on your database of choice:


--SQL Eight Queens

--Create the board:
CREATE TABLE rows (
id integer PRIMARY KEY);
INSERT INTO rows (id) VALUES (1),(2),(3),(4),(5),(6),(7),(8);

CREATE TABLE cols (
id integer PRIMARY KEY);
INSERT INTO cols (id) VALUES (1),(2),(3),(4),(5),(6),(7),(8);

--Get a set of queens:
SELECT
cols.id AS col1, rows.id AS row1,
col2, row2,
col3, row3,
col4, row4,
col5, row5,
col6, row6,
col7, row7,
col8, row8
FROM rows, cols, (SELECT
col3, row3,
col4, row4,
col5, row5,
col6, row6,
col7, row7,
col8, row8,
rows.id AS row2, cols.id AS col2
FROM rows, cols, (SELECT
col4, row4,
col5, row5,
col6, row6,
col7, row7,
col8, row8,
rows.id AS row3, cols.id AS col3
FROM rows, cols, (SELECT
col5, row5,
col6, row6,
col7, row7,
col8, row8,
rows.id AS row4, cols.id AS col4
FROM rows, cols, (SELECT
col6, row6,
col7, row7,
col8, row8,
rows.id AS row5, cols.id AS col5
FROM rows, cols, (SELECT
col7, row7,
col8, row8,
rows.id AS row6, cols.id AS col6
FROM rows, cols, (SELECT
col8, row8,
rows.id AS row7, cols.id AS col7
FROM rows, cols, (SELECT
rows.id AS row8, cols.id AS col8
FROM rows, cols)
AS b8
WHERE cols.id != col8 AND rows.id != row8 --This checks rook moves
AND (cols.id + rows.id != col8 + row8) --This checks bishop moves
AND (cols.id - rows.id != col8 - row8)
) AS b7
WHERE cols.id != col8 AND rows.id != row8
AND cols.id != col7 AND rows.id != row7
AND (cols.id + rows.id != col8 + row8) AND (cols.id - rows.id != col8 - row8)
AND (cols.id + rows.id != col7 + row7) AND (cols.id - rows.id != col7 - row7)
) AS b6
WHERE cols.id != col8 AND rows.id != row8
AND cols.id != col7 AND rows.id != row7
AND cols.id != col6 AND rows.id != row6
AND (cols.id + rows.id != col8 + row8) AND (cols.id - rows.id != col8 - row8)
AND (cols.id + rows.id != col7 + row7) AND (cols.id - rows.id != col7 - row7)
AND (cols.id + rows.id != col6 + row6) AND (cols.id - rows.id != col6 - row6)
) AS b5
WHERE cols.id != col8 AND rows.id != row8
AND cols.id != col7 AND rows.id != row7
AND cols.id != col6 AND rows.id != row6
AND cols.id != col5 AND rows.id != row5
AND (cols.id + rows.id != col8 + row8) AND (cols.id - rows.id != col8 - row8)
AND (cols.id + rows.id != col7 + row7) AND (cols.id - rows.id != col7 - row7)
AND (cols.id + rows.id != col6 + row6) AND (cols.id - rows.id != col6 - row6)
AND (cols.id + rows.id != col5 + row5) AND (cols.id - rows.id != col5 - row5)
) AS b4
WHERE cols.id != col8 AND rows.id != row8
AND cols.id != col7 AND rows.id != row7
AND cols.id != col6 AND rows.id != row6
AND cols.id != col5 AND rows.id != row5
AND cols.id != col4 AND rows.id != row4
AND (cols.id + rows.id != col8 + row8) AND (cols.id - rows.id != col8 - row8)
AND (cols.id + rows.id != col7 + row7) AND (cols.id - rows.id != col7 - row7)
AND (cols.id + rows.id != col6 + row6) AND (cols.id - rows.id != col6 - row6)
AND (cols.id + rows.id != col5 + row5) AND (cols.id - rows.id != col5 - row5)
AND (cols.id + rows.id != col4 + row4) AND (cols.id - rows.id != col4 - row4)
) AS b3
WHERE cols.id != col8 AND rows.id != row8
AND cols.id != col7 AND rows.id != row7
AND cols.id != col6 AND rows.id != row6
AND cols.id != col5 AND rows.id != row5
AND cols.id != col4 AND rows.id != row4
AND cols.id != col3 AND rows.id != row3
AND (cols.id + rows.id != col8 + row8) AND (cols.id - rows.id != col8 - row8)
AND (cols.id + rows.id != col7 + row7) AND (cols.id - rows.id != col7 - row7)
AND (cols.id + rows.id != col6 + row6) AND (cols.id - rows.id != col6 - row6)
AND (cols.id + rows.id != col5 + row5) AND (cols.id - rows.id != col5 - row5)
AND (cols.id + rows.id != col4 + row4) AND (cols.id - rows.id != col4 - row4)
AND (cols.id + rows.id != col3 + row3) AND (cols.id - rows.id != col3 - row3)
) AS b2
WHERE cols.id != col8 AND rows.id != row8
AND cols.id != col7 AND rows.id != row7
AND cols.id != col6 AND rows.id != row6
AND cols.id != col5 AND rows.id != row5
AND cols.id != col4 AND rows.id != row4
AND cols.id != col3 AND rows.id != row3
AND cols.id != col2 AND rows.id != row2
AND (cols.id + rows.id != col8 + row8) AND (cols.id - rows.id != col8 - row8)
AND (cols.id + rows.id != col7 + row7) AND (cols.id - rows.id != col7 - row7)
AND (cols.id + rows.id != col6 + row6) AND (cols.id - rows.id != col6 - row6)
AND (cols.id + rows.id != col5 + row5) AND (cols.id - rows.id != col5 - row5)
AND (cols.id + rows.id != col4 + row4) AND (cols.id - rows.id != col4 - row4)
AND (cols.id + rows.id != col3 + row3) AND (cols.id - rows.id != col3 - row3)
AND (cols.id + rows.id != col2 + row2) AND (cols.id - rows.id != col2 - row2)
LIMIT 1337; --Arbitrary, you can let yours go all day.
--Note that this won't return very many unique solutions (unless your queens have numbers written on them)

I realize that this could be more elegant by trimming out the hard-coded values, and that I could set it up for N queens, but I got excited when it ran for 8. I wrote a nonrecursive brute-force version that ended as expected, with me sighing and restarting Postgres. If I go and edit it, it’ll certainly be to put the results in a human-readable form. Because it’s really cool, but isn’t smart enough to choose good placements ahead of time, I give myself 7 Queens out of a possible 8: