The puzzle is to place eight queens on a chessboard so that no two queens attack each other. The problem is old and has been well studied, the Rosetta Code has solutions for more than 80 programming languages, SQL included.
However, the Rosetta’s SQL solution is implementing a recursive algorithm in SQL, as opposed to a relational approach. In this article I will use a relational design approach to the problem, and then translate that to SQL. The main idea is to design using natural language and concepts of domains, predicates, constraints, sets, set operations, and relations.
The logical design process is database agnostic; for the initial code samples I will use PostgreSQL, which can later be translated to other SQL dialects.
Domains
A domain is simply a set of all possible values over which a variable of interest may range.
The board is composed of 64 named squares, organised in eight rows and eight columns; rows and columns are labelled.
square_name = {'a1' .. 'h8'} -- set of square names
row_lbl = {'1' .. '8'} -- set of row labels
col_lbl = {'a' .. 'h'} -- set of column labels
It is convenient to refer to a square by an offset from another one (say +/-1), so I will assign ordinal numbers to rows and columns.
ordinal_num = {1 .. 8} -- set of ordinal numbers
-- for rows and columns.
Two queens attack each other if they are placed on the same row, column or diagonal. A queen moves in straight lines; so I will use a generic term line to designate a row, a column or a diagonal.
A line (row, column, or diagonal) is a set of squares. To solve the puzzle two queens can not be placed on a square belonging to the same line.
In order to identify a line I will use a starting square (anchor) and direction of motion. For example column b can be identified with an anchor b1 and direction UP; diagonal a2:g8 would have anchor a2 and direction right-up. So, this introduces set of anchors and set of movement directions.
mov_dir = {'UP', 'RGHT', 'RGHT-UP', 'RGHT-DN'}
An anchor is a square identified by its name, hence a set of anchor names is a proper subset of the set of square names; more about anchors a bit later.
SQL Implementation
The reasoning about domains can be nicely translated to PostgreSQL using types; here is the part 1 of the code. The translation from the reasoning to the code is straightforward, which was the idea in the first place.
Next time: predicates, constraints, relations.