# Solving the Eight Queens problem using SAP HANA

I was inspired by Wenjun Zhou who wrote Play the game of life with SAP HANA to have a little fun and solve the Eight Queens problem using SAP HANA.

The Eight Queens is a classic problem in computer science: how can we place eight queens on a chess board, so that none of them can take each other? This is often taught to computer scientists, because it requires use of a backtracking algorithm to solve. I learnt this in a Modula-3 course back in the mid-90s. Here’s a picture of the solution thanks to Eight queens puzzle – Wikipedia, the free encyclopedia

It turns out that there are exactly 92 solutions to this problem on an 8×8 board. I can still remember my Modula-3 program spitting out solutions on a Sun UNIX server. The SQL Server Pro folks, wrote a blog Use T-SQL to Solve the Classic Eight Queens Puzzle which I then adapted to SQLScript. It’s quite elegant, because it first only considers solutions where the queens are in distinct columns. This massively reduces the result space from n^n to n! (40320 for an 8×8 board).

It’s even more fascinating if you do a PlanViz on this, because it only materializes 1704 rows at the most – it doesn’t materialize the whole 40320 result set before it filters. Another example of the efficiency of the HANA column store engine.

I wrote a little piece to create an array of size N to represent the rows, which would be generic, but I couldn’t figure out a way to recurse like you can in T-SQL. Can anyone see a more elegant solution?

DROP PROCEDURE queens;

CREATE PROCEDURE queens ()

LANGUAGE SQLSCRIPT

SQL SECURITY INVOKER

READS SQL DATA AS

BEGIN

DECLARE v_queens INTEGER ARRAY;

DECLARE v_n INTEGER;

FOR v_n IN 1 .. 8 DO

v_queens[:v_n] := :v_n;

END FOR;

queens = UNNEST(:v_queens) AS (n);

SELECT a.n AS a, b.n AS b, c.n AS c, d.n AS D,

e.n AS e, f.n AS f, g.n AS g, h.n AS h

FROM :queens AS a

JOIN :queens AS b

ON b.n <> a.n

and (b.n – a.n) NOT IN (-1, +1)

JOIN :queens AS c

ON c.n NOT IN (a.n, b.n)

AND (c.n – a.n) NOT IN (-2, +2)

AND (c.n – b.n) NOT IN (-1, +1)

JOIN :queens AS d

ON d.n NOT IN (a.n, b.n, c.n)

AND (d.n – a.n) NOT IN (-3, +3)

AND (d.n – b.n) NOT IN (-2, +2)

AND (d.n – c.n) NOT IN (-1, +1)

JOIN :queens AS e

ON e.n NOT IN (a.n, b.n, c.n, d.n)

AND (e.n – a.n) NOT IN (-4, +4)

AND (e.n – b.n) NOT IN (-3, +3)

AND (e.n – c.n) NOT IN (-2, +2)

AND (e.n – d.n) NOT IN (-1, +1)

JOIN :queens AS f

ON f.n NOT IN (a.n, b.n, c.n, d.n, e.n)

AND (f.n – a.n) NOT IN (-5, +5)

AND (f.n – b.n) NOT IN (-4, +4)

AND (f.n – c.n) NOT IN (-3, +3)

AND (f.n – d.n) NOT IN (-2, +2)

AND (f.n – e.n) NOT IN (-1, +1)

JOIN :queens AS g

ON g.n NOT IN (a.n, b.n, c.n, d.n, e.n, f.n)

AND (g.n – a.n) NOT IN (-6, +6)

AND (g.n – b.n) NOT IN (-5, +5)

AND (g.n – c.n) NOT IN (-4, +4)

AND (g.n – d.n) NOT IN (-3, +3)

AND (g.n – e.n) NOT IN (-2, +2)

AND (g.n – f.n) NOT IN (-1, +1)

JOIN :queens AS h

ON h.n NOT IN (a.n, b.n, c.n, d.n, e.n, f.n, g.n)

AND (h.n – a.n) NOT IN (-7, +7)

AND (h.n – b.n) NOT IN (-6, +6)

AND (h.n – c.n) NOT IN (-5, +5)

AND (h.n – d.n) NOT IN (-4, +4)

AND (h.n – e.n) NOT IN (-3, +3)

AND (h.n – f.n) NOT IN (-2, +2)

AND (h.n – g.n) NOT IN (-1, +1)

ORDER BY a, b, c, d, e, f, g;

END;

CALL queens();

Unfortunately there are some extremely efficient solutions to the N Queens problem like Jeff Somers’s N Queens Solutions using C++, and the SQL solution can’t compare to these for this type of problem. I tried running a 16×16 version of this and it was extremely slow.

Still, it was a little fun. I hope you enjoy.

Hi John,

That's cool! Good job! Can't wait to try this. ðŸ™‚

Best regards,

Wenjun

Thanks, just a little fun whilst I was flying home.

hat off John, fantastic

reminds me of Battle Chess visualising the execution.

Andy.

Wow yes I remember that game on the http://en.wikipedia.org/wiki/Acorn_Archimedes

Somewhere, there are some unpleasant parts of the Linux kernel for the Archimedes, with my grubby paws on them.

Hi John,

I slept with this problem in my mind trying to sort something out, this together with another wish

I just want 5% of John Appleby "blog power" . ðŸ˜‰

Kudos

Regards, Fernando Da Rós

I was hoping someone might come up with a solution to make it generic to N Queens, but I can't see a way to do this in SQLScript!

Thanks, you're far too kind ðŸ™‚