Eight Queens in SQL [3]

The third article in the series.

Links to all previous and this post’s code.
Part Main Topic Code (pgSQL)
1 Domains, Types part 1
2 Predicates, Constraints, Relations part 2
3 Propositions and Facts part 3

Relation Values

To populate tables simply run the code; it is self explanatory. You may want to keep an eye on the model while reading the code.

Propositions and Facts

A proposition is a declarative sentence, which can be evaluated (flagged) as true or false. A fact is a proposition considered to be true.

Starting with an example:

SELECT * from board;

SQUARE  CL   RW
---------------
  a1    a    1
  a2    a    2
  ... 
  h8    h    8

consider the result in conjunction with the predicate: [p_03] the board square named (SQUARE) is located in the row labelled (RW) and the column labelled (CL).

Substituting predicate variables with values from the query results in a set of facts, a set of declarative sentences considered to be true.

The board square named 'a1' is located in the row labelled 'a' and the column labelled '1'.

The board square named 'a2' is located in the row labelled 'a' and the column labelled '2'.

...

The board square named 'h8' is located in the row labelled 'h' and the column labelled '8'.

Each of these sentences can be seen as as a term that evaluates to true, hence it is possible to look at the relation board and the matching predicate [p_03] as a function:

board::(SQUARE, RW, CL) → TRUE

-- or more general

board::(SQUARE, RW, CL) → Boolean

So, board is a Boolean function with three parameters: SQUARE, RW, and CL.

Staring with the function board and knowing keys of the relation ({SQUARE}, {RW, CL}) it is easy to derive few related functions.

board::(SQUARE, RW, CL) → TRUE


f1:: SQUARE → (RW, CL) -- returns pair

f2::(RW, CL) → SQUARE

f3:: RW → {SQUARE} -- returns set

f4:: CL → {SQUARE} -- returns set

It takes just a bit of mental exercise to see things this way, and I would encourage you to practice a bit. Once and for all, the exercise will liberate you from the association of the term “relational” with “something to do with a square-shaped data-storage“, which happens to be the popular opinion.

Towards the Solution

It it easy to see how this thinking can be applied to the relation square_line and the matching predicate [p_05].

square_line::(SQUARE, ANCHOR, MOV_DIR) → TRUE

g1:: SQUARE  → {(ANCHOR, MOV_DIR)}

g2::{SQUARE} → {(ANCHOR, MOV_DIR)}

g3:: (ANCHOR, MOV_DIR)  → {SQUARE}

g4::{(ANCHOR, MOV_DIR)} → {SQUARE}

Look at the board and consider the query:

select * 
from square_line
where square in ('c5', 'f2');

square   anchor    mov_dir
---------------------------
  c5       a3      RGHT-UP
  c5       a5      RGHT
  c5       a7      RGHT-DN
  c5       c1      UP
  f2       a2      RGHT
  f2       a7      RGHT-DN
  f2       e1      RGHT-UP
  f2       f1      UP

Given the predicate [p_05], the result is a set of facts:

The square named 'c5' is located on the line identified by the starting square 'a3' and the direction of movement 'RGHT-UP'.

The square named 'c5' is located on the line identified by the starting square 'a5' and the direction of movement 'RGHT'.

The square named 'c5' is located on the line identified by the starting square 'a7' and the direction of movement 'RGHT-DN'.

The square named 'c5' is located on the line identified by the starting square 'c1' and the direction of movement 'UP'.

The square named 'f2' is located on the line identified by the starting square 'a2' and the direction of movement 'RGHT'.

The square named 'f2' is located on the line identified by the starting square 'a7' and the direction of movement 'RGHT-DN'.

The square named 'f2' is located on the line identified by the starting square 'e1' and the direction of movement 'RGHT-UP'.

The square named 'f2' is located on the line identified by the starting square 'f1' and the direction of movement 'UP'.

Suppose two queens are placed on the board, on squares ‘c5’ and ‘f2’:

select anchor, mov_dir
from square_line
where square = 'c5'

intersect

select anchor, mov_dir
from square_line
where square = 'f2'
;

anchor  mov_dir
---------------------------
  a7    RGHT-DN

This fact may be verbalised as:

The queens are located on the line identified by the starting square 'a7' and the direction of movement 'RGHT-DN'.

Now change ‘f2’ to ‘g2’ and run the query.
Next time: the algorithm and the solution to the puzzle.