The N-queen problem: Place N chess queens on an N x N chess board, such that none of the queens can hit each other.
The N-queen problem is a classical Prolog problem, often used to illustrate a generate and test solution strategy.
The solution here is equally classical: It relies on some pre-analysis of the problem and handy representation.
- Since a queen can hit horizontally there can at most be one queen in each row.
- So to place N queens on an N x N board there must be exactly one queen in each row.
So in each row there is exactly one queen which is placed in some column. So we can represent ways to place queens in rows by listing which column that carries a queen for each row.
- the first row has a queen in column 3
- the second row has a queen in column 3
- the third row has a queen in column 2
- Since a queen can hit vertically, there can at most be one queen in each column.
- So to place N queens on an N x N board there must be exactly one queen in each column.
So the list representing the position must contain the numbers from 1 to N, each occurring exactly once.
Hence the possible solutions are permutations of the list [1,2,...,N].
Generate and Test
The generate and test method will generate all permutations of the list [1,2,...,N] and test which ones that are solutions.
We use a list comprehension to build the list [1,2,...,N].
We create all permutations of a list by inserting the fist element at all places in all permutations of the rest of the list.
Given the pre-analysis above we have dealth with the horizontal and vertical hitting, so to test whether something is a solution we only need to consider diagonal hits. Queens can hit diagonally if the vertical distance is the same as the horizontal distance. First we test whether the first queen can hit any other the other queens, then we test whether some of the remaining queens can hit each other (using same starategy).
implement main clauses run() :- console::init(), nqueen(7). class facts count : integer := 0. class predicates nqueen : (integer N). clauses nqueen(N) :- count := 0, InitBoard = [ I || I = std::fromTo(1, N) ], foreach B = permute_nd(InitBoard) do if isSolution(B) then stdio::writef("Solution: %\n", B), count := count+1 end if end foreach, stdio::writef("Found % solutions to the %-queen problem", count, N). class predicates permute_nd : (A*) -> A* nondeterm. clauses permute_nd() = . permute_nd([H|T]) = insert_nd(H, permute_nd(T)). class predicates insert_nd : (A, A*) -> A* multi. clauses insert_nd(X, L) = [X|L]. insert_nd(X, [Y|L]) = [Y|insert_nd(X,L)]. class predicates isSolution : (integer* Board) determ. clauses isSolution(). isSolution([Q|QL]) :- cannotHit(Q, 1, QL), isSolution(QL). class predicates cannotHit : (integer Q, integer DistX, integer* QL) determ. clauses cannotHit(_Q, _Dist, ). cannotHit(Q, DistX, [QDistX|QL]) :- DistY = math::abs(Q-QDistX), DistX <> DistY, cannotHit(Q, DistX+1, QL). end implement main