Technology Blogs by Members
Explore a vibrant mix of technical expertise, industry insights, and tech buzz in member blogs covering SAP products, technology, and events. Get in the mix!
cancel
Showing results for 
Search instead for 
Did you mean: 
Former Member
2,935

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 8x8 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 8x8 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 16x16 version of this and it was extremely slow.


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

6 Comments
Labels in this area