1% BEGIN LICENSE BLOCK
2% Version: CMPL 1.1
3%
4% The contents of this file are subject to the Cisco-style Mozilla Public
5% License Version 1.1 (the "License"); you may not use this file except
6% in compliance with the License.  You may obtain a copy of the License
7% at www.eclipse-clp.org/license.
8%
9% Software distributed under the License is distributed on an "AS IS"
10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11% the License for the specific language governing rights and limitations
12% under the License.
13%
14% The Original Code is  The ECLiPSe Constraint Logic Programming System.
15% The Initial Developer of the Original Code is  Cisco Systems, Inc.
16% Portions created by the Initial Developer are
17% Copyright (C) 1994-2006 Cisco Systems, Inc.  All Rights Reserved.
18%
19% Contributor(s): ECRC GmbH.
20%
21% END LICENSE BLOCK
22
23%
24% The N-queens puzzle. We have to place N queens on an NxN chess boards
25% so that no-one can take another one. Our model is:
26%
27%        Variables: N variables with domain 1..N, each variable represents
28%                        the position of a queen in one column
29%        Constraints:
30%                1) all columns are different - IMPLICIT
31%                2) all rows are different
32%                3) no diagonal has more than one queen
33%
34
35
36:- lib(fd).
37:- lib(grace).                                 % Grace
38
39queens(N, List) :-
40    grace_start(queens),                       % Grace
41
42    % Define variables and their domains
43    length(List, N),
44    List :: 1..N,
45    grace_matrix(List, queens),                % Grace
46
47    % Constraints
48    %2
49    alldistinct(List),
50    %3
51    constrain_queens(List),
52
53    % Label the variables
54    grace_label.                               % Grace
55
56% A queen is safe if it cannot be taken by
57% any of its right-hand neigbours
58constrain_queens([]).
59constrain_queens([X|Y]) :-
60   safe(X, Y, 1),
61   constrain_queens(Y).
62
63safe(_, [], _).
64safe(Q1, [Q2|T], N) :-
65   % Q1 and Q2 are not on the same diagonal
66   Q1 - Q2 #\= N,
67   Q2 - Q1 #\= N,
68   N1 is N + 1 ,
69   safe(Q1, T, N1).
70
71