A comparison of solutions of a textbook problem
The problem
The problem, well-known, is to place 8 queens on a chess-board
so that no queen can capture any other queen.
Since each row and column must contain exactly one queen,
it suffices to represent the solution with
a permutation of the first 8 digits, e.g., [4,6,1,5,2,8,3,7],
with the following convention.
The i-th element of the permutation
is the row where the queen in column i is placed.
Referring to the example, there is a queen in row 4 of column 1,
a queen in row 6 of column 2, etc.
The functional solution
The functional solution is from R. Bird and P. Wadler, Introduction
to Functional Programming, Prentice Hall, 1988, pages 161-165.
The language is
(Hugs 1.3) Haskell.
queens 0 = [[]]
queens (m+1) = [p++[n] | p <- queens m, n <- [1..8], safe p n]
safe p n = and [not (check (i,j) (m,n)) | (i,j) <- zip [1..(length p)] p] where m = length p+1
check (i,j) (m,n) = (j==n) || (i+j == m+n) || (i-j == m-n)
To compute a placement execute
hd (queens 8).
The logic solution
The logic solution is from R. A. O'Keefe, The Craft of Prolog,
The MIT Press, 1990, pages 132-135.
The language is
(SICStus 2.1) Prolog.
queens(N, Queens) :-
length(Queens, N),
board(Queens, Board, 0, N, _, _),
queens(Board, 0, Queens).
board([], [], N, N, _, _).
board([_|Queens], [Col-Vars|Board], Col0, N, [_|VR], VC) :-
Col is Col0+1,
functor(Vars, f, N),
constraints(N, Vars, VR, VC),
board(Queens, Board, Col, N, VR, [_|VC]).
constraints(0, _, _, _) :- !.
constraints(N, Row, [R|Rs], [C|Cs]) :-
arg(N, Row, R-C),
M is N-1,
constraints(M, Row, Rs, Cs).
queens([], _, []).
queens([C|Cs], Row0, [Row-Col|Solution]) :-
Row is Row0+1,
select(Col-Vars, [C|Cs], Board),
arg(Row, Vars, Row-Row),
queens(Board, Row, Solution).
select(X, [X|R], R).
select(X, [H|T], [H|R]) :-
select(X, T, R).
To compute a placement execute
queens(8,Queens).
The functional logic solution
The functional logic program is, for the most part,
a constructor-based conditional rewrite systems where
rewrite rules are expressed in familiar programming notations.
Function capture
is a constraint, i.e., a function that similar to a Prolog predicate
succeeds if its condition succeeds.
Indentifier void
denotes a primitive constraint that
succeeds if its argument has no solutions.
queens N -> Y :- X = 1..N, Y = permute X, void (capture Y).
permute [] -> [].
permute [X|Xs] -> U++[X]++V :- U++V = permute Xs.
capture Y :- _++[Y1]++K++[Y2]++_ = Y, abs(Y1-Y2) = length K+1.
To compute a placement execute
queens 8.
This program relies on features that could not be coded in
either the functional or logic version (or both).
- Non-determinism
e.g., the non-determinate function
permute
returns one of many values.
- Semantic unification
e.g., uninstantiated variables in the expression
U++V = permute Xs
are instantiated, if possible, to satisfy the equation.
- Functional inversion
e.g., the expression
_++[Y1]++K++[Y2]++_
is used not to concatenate lists, but to extract
(lazily and non-deterministically) two element from a list
(of pairs of integers).
Non-determinism and logic variables are unavailable
in functional languages, whereas
nested, lazily-evaluated functional expressions
are unavailable in logic languages
A language with these features and more, though with a different syntax,
is currently being designed and implemented,
see
Curry.