This is the fourth and final part of the series showing how to solve the “Eight Queens” chess puzzle, using a database design and SQL. The main idea is to design using natural language and concepts of domains, predicates, constraints, sets, set operations, and relations.
| Part | Main Topic | Code (pgSQL) |
|---|---|---|
| 1 | Domains, Types | part 1 |
| 2 | Predicates, Constraints, Relations | part 2 |
| 3 | Propositions and Facts | part 3 |
| 4 | The Algorithm and the Solution | part 4 |
Algorithm
Say we place a queen, Q1, on square c5, the queen will cover row 5, column c, and diagonals a3:f8 and a7:g1. Each one of these is a line (a set of squares), so the square c5 is an element of each of these four sets. Using the (anchor, movement direction) notation to identify a line, the following holds:
row 5 = ('a5', 'RGHT') = {'a5' ... 'h5'}
column c = ('c1', 'UP') = {'c1' ... 'c8'}
diagonal a3:f8 = ('a3', 'RGHT-UP') = {'a3' ... 'f8'}
diagonal a7:g1 = ('a7', 'RGHT-DN') = {'a7' ... 'g1'}
'c5' ∈ ('a5', 'RGHT')
'c5' ∈ ('c1', 'UP')
'c5' ∈ ('a3', 'RGHT-UP')
'c5' ∈ ('a7', 'RGHT-DN')
Let’s introduce a set, L1, which is the set of these four lines; note that L1 is a set of sets.
L1 = { ('a5', 'RGHT') , ('c1', 'UP'),
('a3', 'RGHT-UP'), ('a7', 'RGHT-DN')
}
'c5' ∈ ⋃ L1
⋂ L1 = {'c5'}
⋃ L1 is the union of all sets in L1, and represents all squares that the queen placed on c5 attacks. ⋂ L1 is the intersection of these sets and it has only one element, the c5 square itself.
Now let’s place another queen, Q2, on square f2; using the reasoning from the previous example, the following holds:
L2 = { ('a2', 'RGHT') , ('f1', 'UP'),
('e1', 'RGHT-UP'), ('a7', 'RGHT-DN')
}
'f2' ∈ ⋃ L2
⋂ L2 = {'f2'}
The rule that two queens attack each other if placed on the same line (row, column or diagonal) can be expressed as an intersection between sets L1 and L2. If the intersection is an empty set then they do not attack each other, otherwise they do; in this example they both have one diagonal in common.
L1 ⋂ L2 = {('a7', 'RGHT-DN')}
Suppose that eight queens Q1 … Q8 are placed on a chessboard one by one. As queen Qn is placed on a square we calculate the corresponding set Ln. The intersection of set Ln — for the queen being placed — and union of all previous L1 … Ln-1 sets — for queens already on the board — must be an empty set.
Queen Rule for placement
Q1 L1 ⋂ {} = {} -- always True
Q2 L2 ⋂ L1 = {}
Q3 L3 ⋂ (L1 ⋃ L2) = {}
Q4 L4 ⋂ (L1 ⋃ L2 ⋃ L3) = {}
Q5 L5 ⋂ (L1 ⋃ L2 ⋃ L3 ⋃ L4) = {}
Q6 L6 ⋂ (L1 ⋃ L2 ⋃ L3 ⋃ L4 ⋃ L5) = {}
Q7 L7 ⋂ (L1 ⋃ L2 ⋃ L3 ⋃ L4 ⋃ L5 ⋃ L6) = {}
Q8 L8 ⋂ (L1 ⋃ L2 ⋃ L3 ⋃ L4 ⋃ L5 ⋃ L6 ⋃ L7) = {}
In general, to place queen Qn on the board, the following must hold:
⋃{L1 ... Ln-1} ⋂ Ln = {}
This now looks like an algorithm; although it does appear recursive, I will avoid recursion in this example.
Reducing the Search Space
A solution to the problem is in the form of:
{s1, s2, s3, s4, s5, s6, s7, s8}
sn ∈ square_name
where sn is a square identified by a square name.
In general, there is more than one solution to the puzzle, hence the
final result is a set of all possible solutions:
{
{s1.1, s1.2, s1.3, s1.4, s1.5, s1.6, s1.7, s1.8}
, {s2.1, s2.2, s2.3, s2.4, s2.5, s2.6, s2.7, s2.8}
, ...
}
si.n ∈ square_name
The idea is now to estimate the search space for which the placement rules have to be evaluated, and reduce it as much as possible by reasoning about the problem.
In the first estimate we can start with reasoning that the first queen can be placed on one out of 64 squares, second on one out of 63, third on one out of 62, etc. The number of permutations here is 64! / (64-8)! = 1.78E+14.
However, the order of queens within one solution does not matter, so we should use combinations instead and choose 8 out of 64 — (64! / (8! x (64-8)!) = 4.43E+9.
Given that two queens can not be placed in the same column, we can start placing them column by column, so each queen can be placed on a maximum of eight squares — one column. This brings down the number of combinations to 8^8 = 1.68E+7.
Given that two queens can not be in the same row, each subsequent placement has one square less available than the previous one; this now brings number of combinations to 8! = 40320.
Further improvement can be made avoiding rows +/-1 from the queen in the previous column. For example, if the first queen was placed in column ‘a’, row 4, then the second queen can be placed in column ‘b’, but not in rows 3, 4 or 5; this further reduces the number of possible combinations to 5424.
To summarize the reasoning about number of combinations involved:
| Reasoning | Calc | Search Space |
|---|---|---|
| Permute 8 out of 64 | 64! / (64-8)! | 1.78E+14 |
| Choose 8 out of 64 | 64! / (8! x (64-8)!) | 4.43E+9 |
| By column | 8^8 | 1.68E+7 |
| By column, avoid previous rows | 8! | 40320 |
| By column, avoid previous rows, avoid row +/-1 from the queen in the previous column. |
Simply count | 5424 |
This looks quite feasible; in total the placement rules argued in the algorithm section have to be evaluated for 5424 combinations.
Solution
Take a look at the code; the result is implemented as a single query in a view named solution.
There are 92 possible solutions to the puzzle:
select * from solution; s1 s2 s3 s4 s5 s6 s7 s8 ------------------------------ a1 b5 c8 d6 e3 f7 g2 h4 a1 b6 c8 d3 e7 f4 g2 h5 ... a8 b3 c1 d6 e2 f5 g7 h4 a8 b4 c1 d3 e6 f2 g7 h5
It should be easy to read the code and the reasoning section in parallel, which has been the main guiding principle of this exercise.
The first part of the query — CTE named w — reduces the search space as described in the previous section. Consider the step of placing queen Q3 on column c:
JOIN board1 as q3
ON q3.CL = 'c'
and q3.RW not in (q1.RW, q2.rw)
and q3.RW_NO not BETWEEN (q2.RW_NO - 1)
and (q2.RW_NO + 1)
The predicate in the join condition is selecting the column c, avoiding the rows of the two previously placed queens, and avoiding rows +/- 1 from the queen next to it (Q2).
The CTE w returns a set of tuples — the reduced search space — then the second part of the query applies the rules (constraints) from the algorithm section to this set.
Using queen Q3 as an example, the rule for placement:
L3 ⋂ (L1 ⋃ L2) = {}
is implemented as:
and not exists ( -- placing queen 3
SELECT distinct e.ANCHOR, e.MOV_DIR
FROM square_line as e
WHERE e.SQUARE in (w.s1, w.s2)
INTERSECT
SELECT distinct e.ANCHOR, e.MOV_DIR
FROM square_line as e
WHERE e.SQUARE = w.s3
)
Evaluating the Solution
When evaluating a solution to a problem, I tend to focus on the following criteria:
- Correctness.
- Ability to reason about the code and the problem now.
- Ability to reason about the code and the problem in the future. Suppose that this happens to be a part of a much larger project, and ten years from now a “third generation” of developers has to understand the code. How hard will it be?
- Ability to change technology and scale in size. Instead of arguing that this approach can easily scale and change technologies, I will simply present it in a few future posts.
- Performance: although I did not even attempt to optimize queries — and have given priority to readability and reasoning — the solution runs reasonably well.
I encourage you to compare this to Rosetta’s implementation — and a few more — using all of the criteria.