N-queen puzzle

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.

Pre-analysis

• 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.

Example [3,3,2] represents a board where:

• 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

See also

wikipedia:Eight queens puzzle