05. 06. 2023 William Calliari Development

About Set Theory, the N-queens Problem, and SQL

The n-queens problem is a common exercise in computer science. Legend has it that a mathematician once declared that women are like the queens in chess, you can’t put eight of them in a room without them trying to kill each other. This obviously isn’t true, and since I’m a feminist, but also a nerd, we will disprove him today in an unconventional way: with an SQL query.

Let me give you a quick overview of the problem:

In chess the queen can move any number of squares vertically, horizontally or diagonally. This means, if two queens are in the same row, the same column or diagonal to one another, they can attack each other. The problem requires us to place n queens on a n-by-n board without any of them being able to attack each other, or in more technical terms, we are looking for the set of all sets with cardinality n such that no two queens in that set can attack each other. If that set is non-empty, then we have disproven the claim.

Modeling the problem

Normally this problem would be solved iteratively with an algorithm, however this is not possible in SQL. Therefore we have to reach back to set theory to model the problem in a language that translates well to SQL.

First we need a set of all positions a queen can be in. For that we model a queen as a tuple of two coordinates in the n-by-n grid:Error

possible_positions = { ( x, y ) | x, y ∈ [ 1 , n ] }

After that we need a set of all combinations with queens. This set of possible positions grows quadratically with the length of the board, described by the function ((n²! ) / ( n² – n )! ) / n!. That’s because we have n²! possible combinations of queen positions on the board without stacking any on top of each other. However (n²–n)! of those are sets with more than n queens on the board. After that we have all combinations duplicated n! times as permutations of each other. We are, however, only interested in single solutions without considering those permutations. With this we find there exist 1,820 possible combinations for a 4-by-4 board, which is the smallest board with a solution. On a standard 8-by-8 board this number rises to 4,426,165,368.

boards = {board ∈ 𝒫 (possible_positions)|#board = n}

Now that we have that set, we need to filter out all sets that contain queens that can attack each other. To check if they are in the same column or row is trivial. We just have to check if the x or y coordinates of the tuple are equal. However for the diagonals we have to use a trick.

Let’s first list the diagonal fields from the top left to the bottom right out so we get a feel for the data: (1,1), (2,2) .. (8,8). As we can see, in this diagonal both the x and y coordinates grow at the same rate. With that information we can guarantee that the difference between x and y in the same diagonal also stays the same: 1 – 1 = 0, 2 – 2 = 0 .. 8 – 8 = 0. We can use that difference to check weather two queens are in the same diagonal or not.

We can use a similar trick for the other diagonal as well. Let’s list the fields from the top right to the bottom left first: (8,1), (7,2) .. (1,8). Here the x coordinate decreases at the same rate that y increases. Therefore the sum of the coordinates in this diagonal stays the same: 8 + 1 = 9, 7 + 2 = 9 .. 1 + 8 = 9.

With this we now have all our conditions for which queens can attack each other, and we only need to plug them into our final formula to get the expression:

{board ∈ boards|∀(x₁,y₁) ∈ board : ∄ ( x₂,y₂) ∈ board \ (x₁,y₁)such that (x₁=x₂) ∨ (y₁=y₁) ∨ (x₁–y₁=x₂–y₂) ∨ (x₁+y₁) = (x₂+y₂)}

We create the set of all sets of queens with cardinality n, for which it holds that for all queens in that set there does not exist another queen such that they could attack each other horizontally, vertically or diagonally.

Or in plain English: All sets with n queens in them and no two queens can attack one another.

Translating this to SQLThe text contains 3 consecutive sentences starting with the same word. Try to mix things up!

While at first it seems like this logic could be mapped fairly well to SQL, we quickly run into our first problems: this logic works on sets of sets of tuples, however SQL works on sets of tuples. Therefore we have to flatten the sets down to a larger tuple.

However this structure also gives us distinct advantages: We can make assumptions about our data and with that decrease the amount of work that has to be done and stop computation for partial results, if they already don’t fit our criteria.

I will implement the logic here for the smallest board with solutions: the 4-by-4 board, since the implementation get increasingly verbose. However this model can theoretically be increased for all sizes.

But first we need a set of columns on which we can place. We use a recursive common table expression (rCTE) for this to save ourselves a bit work:

WITH RECURSIVE nqueens_columns AS (
    SELECT 4 as queen_column
    UNION
    SELECT queen_column - 1 AS queen_column
    FROM nqueens_columns
    WHERE queen_column > 1
) SELECT * FROM nqueens_columns;

Now we could theoretically create a table for all positions of queens on the board with nested common table expressions to get a set of all possible positions for a queen on a chess board.

WITH RECURSIVE queen_positions AS (
    WITH RECURSIVE nqueens_columns AS (
        SELECT 4 as queen_column
        UNION
        SELECT queen_column - 1 AS queen_column
        FROM nqueens_columns
        WHERE queen_column > 1
    )
    SELECT 4 as queen_row, queen_column
    FROM nqueens_columns
    UNION
    SELECT queen_row - 1 AS queen_row, new_columns.queen_column
    FROM queen_positions JOIN nqueens_columns as new_columns
    WHERE queen_row > 1
) SELECT * FROM queen_positions;

After n cross joins of this table with itself, we would then get a set of all boards with exactly n queens on them, even the boards with queens stacked on top of each other. However this would also result in a lot of wasted work by including many solutions that obviously don’t work. Furthermore it would duplicate all solutions by a factor of n! since the tuple is sorted and therefore all mutations of the same result appear different. This is a tradeoff we have to stomach by mapping the set of tuples, which would avoid such cases, to a tuple that can be processed by an SQL query. The query to filter out duplicates would grow very quickly and would be much more verbose that doing the join by hand. However, by writing the query by hand, we have an alternative.

We can save a lot of work by making assumptions about our data. Remember how I previously mentioned that we have 1,820 possible combinations of queen positions for this board? We know that combinations with queens in the same row can never be in the final result, because they already violate one of the rules. Therefore we can leave them out of the initial set by adding each new queen in a new row. The new set with this simple assumption will still grow exponentially with the function nⁿ, which is a huge space to search, but it’s still far less than what’s needed by the brute-force approach. By including that assumption in our query (and making it a bit more verbose), this query will only return 256 results, saving the computer a lot of time and resources, especially for larger boards.

WITH RECURSIVE nqueens_columns AS (
    SELECT 4 as columns
    UNION
    SELECT columns - 1 AS columns
    FROM nqueens_columns
    WHERE columns > 1
) SELECT * FROM (
    SELECT 1 AS x1, columns AS y1 
    FROM nqueens_columns
) as queen1
JOIN
(
    SELECT 2 AS x2, columns AS y2
    FROM nqueens_columns
) AS queen2
JOIN
(
    SELECT 3 AS x3, columns AS y3
    FROM nqueens_columns
) AS queen3
JOIN
(
    SELECT 4 AS x4, columns AS y4
    FROM nqueens_columns
) AS queen4;

After this we only need to apply our rules to the query, and filter out all sets that contain queens that attack each other. Here we can make another assumption about our data: While it would be easiest to add a where-clause for all restrictions to the end of the query, we can optimize by throwing out partial results that already violate our rules. We check after each join if it clashes with any of the previous queens and only keep those that don’t, reducing the joins that need to be carried out for the remaining queens. For example, after joining in the second queen, we already check if she can attack the first queen. If that’s possible, we can already ignore that without taking any further queens into account. After the third queen, we check if there are clashes with queens one and two and so on.

WITH RECURSIVE nqueens_columns AS (
    SELECT 4 as columns
    UNION
    SELECT columns - 1 AS columns
    FROM nqueens_columns
    WHERE columns > 1
) SELECT * FROM (
    SELECT 1 AS x1, columns AS y1 
    FROM nqueens_columns
) as queen1
JOIN
(
    SELECT 2 AS x2, columns AS y2
    FROM nqueens_columns
) AS queen2
ON NOT (
    y1 = y2
    OR x1 - y1 = x2 - y2
    OR x1 + y1 = x2 + y2
)
JOIN
(
    SELECT 3 AS x3, columns AS y3
    FROM nqueens_columns
) AS queen3
ON NOT (
    y1 = y3
    OR x1 - y1 = x3 - y3
    OR x1 + y1 = x3 + y3
    OR y2 = y3
    OR x2 - y2 = x3 - y3
    OR x2 + y2 = x3 + y3
)
JOIN
(
    SELECT 4 AS x4, columns AS y4
    FROM nqueens_columns
) AS queen4
ON NOT (
    y1 = y4
    OR x1 - y1 = x4 - y4
    OR x1 + y1 = x4 + y4
    OR y2 = y4
    OR x2 - y2 = x4 - y4
    OR x2 + y2 = x4 + y4
    OR y3 = y4
    OR x3 - y3 = x4 - y4
    OR x3 + y3 = x4 + y4
);

With this, we have at last constructed the final query! Now the only thing remaining is to format our output to get actual chess positions, so that the chess players here won’t hunt me down later.

[..] SELECT 
    CONCAT(CHAR(x1 + 64), y1) AS queen1,
    CONCAT(CHAR(x2 + 64), y2) AS queen2,
    CONCAT(CHAR(x3 + 64), y3) AS queen3,
    CONCAT(CHAR(x4 + 64), y4) AS queen4
FROM [..]

The final result is a set with two possible solutions. After a quick check on Wikipedia we can see that we actually found the correct solutions for a 4-by-4 board through a simple SQL query.

+--------+--------+--------+--------+
| queen1 | queen2 | queen3 | queen4 |
+--------+--------+--------+--------+
| A2     | B4     | C1     | D3     |
| A3     | B1     | C4     | D2     |
+--------+--------+--------+--------+

And to answer the question from above, here’s the query for eight queens:

n-queens Download

And in fact we get 92 results, firmly disproving this legendary mathematician.

These Solutions are Engineered by Humans

Did you find this article interesting? Does it match your skill set? Programming is at the heart of how we develop customized solutions. In fact, we’re currently hiring for roles just like this and others here at Würth Phoenix.