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.