Prolog Programming

Question

I have made two programs in Prolog for the nqueens puzzle using hill climbing and beam search algorithms.

Unfortunately I do not have the experience to check whether the programs are correct and I am in dead end.

I would appreciate if someone could help me out on that. Unfortunately the program in hill climbing is incorrect. :( The program in beam search is:

queens(N, Qs) :-  
  range(1, N, Ns), 
  queens(Ns, [], Qs).

range(N, N, [N]) :- !.
range(M, N, [M|Ns]) :- 
  M < N, 
  M1 is M+1, 
  range(M1, N, Ns).

queens([], Qs, Qs).
queens(UnplacedQs, SafeQs, Qs) :- 
  select(UnplacedQs, UnplacedQs1,Q),
  not_attack(SafeQs, Q),  
  queens(UnplacedQs1, [Q|SafeQs], Qs).  

not_attack(Xs, X) :- 
  not_attack(Xs, X, 1).
not_attack([], _, _) :- !.
not_attack([Y|Ys], X, N) :-
  X =\= Y+N,  
  X =\= Y-N, 
  N1 is N+1, 
  not_attack(Ys, X, N1).

select([X|Xs], Xs, X).
select([Y|Ys], [Y|Zs], X) :- select(Ys, Zs, X).

Answer 1

A quick check on Google has found a few candidates for you to compare with your code and find what to change.

My favoured solution for sheer clarity would be the second of the ones linked to above:

% This program finds a solution to the 8 queens problem.  That is, the problem of placing 8
% queens on an 8x8 chessboard so that no two queens attack each other.  The prototype
% board is passed in as a list with the rows instantiated from 1 to 8, and a corresponding
% variable for each column.  The Prolog program instantiates those column variables as it
%  finds the solution.

% Programmed by Ron Danielson, from an idea by Ivan Bratko.

% 2/17/00


queens([]).                                 % when place queen in empty list, solution found

queens([ Row/Col | Rest]) :-                % otherwise, for each row
            queens(Rest),                   % place a queen in each higher numbered row
            member(Col, [1,2,3,4,5,6,7,8]), % pick one of the possible column positions
            safe( Row/Col, Rest).           % and see if that is a safe position
                                            % if not, fail back and try another column, until
                                            % the columns are all tried, when fail back to
                                            % previous row

safe(Anything, []).                         % the empty board is always safe

safe(Row/Col, [Row1/Col1 | Rest]) :-        % see if attack the queen in next row down
            Col =\= Col1,                   % same column?
            Col1 - Col =\= Row1 - Row,      % check diagonal
            Col1 - Col =\= Row - Row1,
            safe(Row/Col, Rest).            % no attack on next row, try the rest of board

member(X, [X | Tail]).                      % member will pick successive column values

member(X, [Head | Tail]) :-
            member(X, Tail).

board([1/C1, 2/C2, 3/C3, 4/C4, 5/C5, 6/C6, 7/C7, 8/C8]). % prototype board

The final link, however, solves it in three different ways so you can compare against three known solutions.

Answer 2

If I read your code correctly, the algorithm you're trying to implement is a simple depth-first search rather than beam search. That's ok, because it should be (I don't see how beam search will be effective for this problem and it can be hard to program).

I'm not going to debug this code for you, but I will give you a suggestion: build the chess board bottom-up with

queens(0, []).
queens(N, [Q|Qs]) :-
    M is N-1,
    queens(M, Qs),
    between(1, N, Q),
    safe(Q, Qs).

where safe(Q,Qs) is true iff none of Qs attack Q. safe/2 is then the conjunction of a simple memberchk/2 check (see SWI-Prolog manual) and your not_attack/2 predicate, which on first sight seems to be correct.

Answer 3

I would like to mention this problem is a typical constraint satisfaction problem and can be efficiency solved using the CSP module of SWI-Prolog. Here is the full algorithm:

:- use_module(library(clpfd)).

queens(N, L) :-
    N #> 0,
    length(L, N),
    L ins 1..N,
    all_different(L),
    applyConstraintOnDescDiag(L),
    applyConstraintOnAscDiag(L),
    label(L).

applyConstraintOnDescDiag([]) :- !.
applyConstraintOnDescDiag([H|T]) :-
    insertConstraintOnDescDiag(H, T, 1),
    applyConstraintOnDescDiag(T).

insertConstraintOnDescDiag(_, [], _) :- !.
insertConstraintOnDescDiag(X, [H|T], N) :-
    H #\= X + N,
    M is N + 1,
    insertConstraintOnDescDiag(X, T, M).

applyConstraintOnAscDiag([]) :- !.
applyConstraintOnAscDiag([H|T]) :-
    insertConstraintOnAscDiag(H, T, 1),
    applyConstraintOnAscDiag(T).

insertConstraintOnAscDiag(_, [], _) :- !.
insertConstraintOnAscDiag(X, [H|T], N) :-
    H #\= X - N,
    M is N + 1,
    insertConstraintOnAscDiag(X, T, M).

N is the number of queens or the size of the board (), and , where , being the position of the queen on the line .

Let's details each part of the algorithm above to understand what happens.

:- use_module(library(clpfd)).

It indicates to SWI-Prolog to load the module containing the predicates for constraint satisfaction problems.

queens(N, L) :-
        N #> 0,
        length(L, N),
        L ins 1..N,
        all_different(L),
        applyConstraintOnDescDiag(L),
        applyConstraintOnAscDiag(L),
        label(L).

The queens predicate is the entry point of the algorithm and checks if the terms are properly formatted (number range, length of the list). It checks if the queens are on different lines as well.

applyConstraintOnDescDiag([]) :- !.
applyConstraintOnDescDiag([H|T]) :-
    insertConstraintOnDescDiag(H, T, 1),
    applyConstraintOnDescDiag(T).

insertConstraintOnDescDiag(_, [], _) :- !.
insertConstraintOnDescDiag(X, [H|T], N) :-
    H #\= X + N,
    M is N + 1,
    insertConstraintOnDescDiag(X, T, M).

It checks if there is a queen on the descendant diagonal of the current queen that is iterated.

applyConstraintOnAscDiag([]) :- !.
applyConstraintOnAscDiag([H|T]) :-
    insertConstraintOnAscDiag(H, T, 1),
    applyConstraintOnAscDiag(T).

insertConstraintOnAscDiag(_, [], _) :- !.
insertConstraintOnAscDiag(X, [H|T], N) :-
    H #\= X - N,
    M is N + 1,
    insertConstraintOnAscDiag(X, T, M).

Same as previous, but it checks if there is a queen on the ascendant diagonal.

Finally, the results can be found by calling the predicate queens/2, such as:

?- findall(X, queens(4, X), L).
L = [[2, 4, 1, 3], [3, 1, 4, 2]]