Archives for category: Puzzles

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;

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: