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) 2006 Cisco Systems, Inc.  All Rights Reserved.
18%
19% Contributor(s):
20%
21% END LICENSE BLOCK
22% Boolean tests from Daniel Diaz
23% 931127 adapted to Eclipse and CHRs by Thom Fruehwirth, ECRC
24
25%From diaz@margaux.inria.fr Tue Nov 23 18:59:17 1993
26%
27%I send you 3 programs schur.pl, pigeon.pl and queens.pl and a file
28%b_bips.pl containing the necessary built-ins and libraries.
29
30
31
32
33%---schur.pl---
34
35/*-------------------------------------------------------------------------*/
36/* Benchmark (Boolean)                  INRIA Rocquencourt - ChLoE Project */
37/*                                                                         */
38/* Name           : bschur.pl                                              */
39/* Title          : Schur's lemma                                          */
40/* Original Source: Giovanna Dore - Italy                                  */
41/* Adapted by     : Daniel Diaz - INRIA France                             */
42/* Date           : January 1993                                           */
43/*                                                                         */
44/* Color the integers 1,2...,N with 3 colors so that there is no monochrome*/
45/* triplets (x,y,z) where x+y=z. Solution iff N<=13.                       */
46/* The solution is a list [ [Int11,Int12,Int13],..., [IntN1,IntN2,IntN3] ] */
47/* where Intij is 1 if the integer i is colored with the color j.          */
48/*                                                                         */
49/* Solution:                                                               */
50/* N=4  [[0,0,1],[0,1,0],[0,0,1],[1,0,0]]                                  */
51/*      [[0,0,1],[0,1,0],[0,1,0],[0,0,1]]                                  */
52/*        ...                                                              */
53/* N=13 [[0,0,1],[0,1,0],[0,1,0],[0,0,1],[1,0,0],[1,0,0],[0,0,1],[1,0,0],  */
54/*       [1,0,0],[0,0,1],[0,1,0],[0,1,0],[0,0,1]] (first solution)         */
55/*-------------------------------------------------------------------------*/
56
57:- [bool]. % load in boolean ECH handler
58
59bschur:-	write('N ?'), read(N),
60	Starttime is cputime,
61	(schur(N,A),
62%	 write(A), nl,
63	 fail
64	   ;
65	 write('No more solutions'), nl),
66	Y is cputime-Starttime,
67	write('time : '), write(Y), nl.
68
69
70
71
72schur(N,A):-
73	create_array(N,3,A),
74	for_each_line(A,only1),
75	pair_constraints(A,A),
76	!,
77%	labeling.
78	array_labeling(A).
79
80
81
82
83pair_constraints([],_):-
84	!.
85
86pair_constraints([_],_):-
87	!.
88
89pair_constraints([_,[K1,K2,K3]|A2],[[I1,I2,I3]|A1]):-
90	and0(I1,K1),
91	and0(I2,K2),
92	and0(I3,K3),
93	triplet_constraints(A2,A1,[I1,I2,I3]),
94	pair_constraints(A2,A1).
95
96
97
98
99triplet_constraints([],_,_).
100
101triplet_constraints([[K1,K2,K3]|A2],[[J1,J2,J3]|A1],[I1,I2,I3]):-
102	and0(I1,J1,K1),
103	and0(I2,J2,K2),
104	and0(I3,J3,K3),
105	triplet_constraints(A2,A1,[I1,I2,I3]).
106
107
108
109
110
111
112%--- pigeon.pl ---
113
114/*-------------------------------------------------------------------------*/
115/* Benchmark (Boolean)                  INRIA Rocquencourt - ChLoE Project */
116/*                                                                         */
117/* Name           : bpigeon.pl                                             */
118/* Title          : pigeon-hole problem                                    */
119/* Originated from:                                                        */
120/* Adapted by     : Daniel Diaz - INRIA France                             */
121/* Date           : January 1993                                           */
122/*                                                                         */
123/* Put N pigeons in M pigeon-holes. Solution iff N<=M.                     */
124/* The solution is a list [ [Pig11,...,Pig1m], ... ,[Pign1,...,Pignm] ]    */
125/* where Pigij = 1 if the pigeon i is in the pigeon-hole j                 */
126/*                                                                         */
127/* Solution:                                                               */
128/* N=2 M=3 [[0,0,1],[0,1,0]]                                               */
129/*         [[0,0,1],[1,0,0]]                                               */
130/*         [[0,1,0],[0,0,1]]                                               */
131/*         [[0,1,0],[1,0,0]]                                               */
132/*         [[1,0,0],[0,0,1]]                                               */
133/*         [[1,0,0],[0,1,0]]                                               */
134/*-------------------------------------------------------------------------*/
135
136
137bpigeon:-	write('N ?'), read(N), write('M ?'), read(M),
138	Starttime is cputime,
139	(bpigeon(N,M,A),
140%	 write(A), nl,
141	 fail
142	   ;
143	 write('No more solutions'), nl),
144	Y is cputime-Starttime,
145	write('time : '), write(Y), nl.
146
147
148
149
150bpigeon(N,M,A):-
151	create_array(N,M,A),
152	for_each_line(A,only1),
153	for_each_column(A,atmost1),
154	!,
155	array_labeling(A).
156
157
158
159
160
161
162
163
164
165%--- queens.pl ---
166
167/*-------------------------------------------------------------------------*/
168/* Benchmark (Boolean)                  INRIA Rocquencourt - ChLoE Project */
169/*                                                                         */
170/* Name           : bqueens.pl                                             */
171/* Title          : N-queens problem                                       */
172/* Original Source: Daniel Diaz - INRIA France                             */
173/* Adapted by     :                                                        */
174/* Date           : January 1993                                           */
175/*                                                                         */
176/* Put N queens on an NxN chessboard so that there is no couple of queens  */
177/* threatening each other.                                                 */
178/* The solution is a list [ [Que11,...,Que1N], ... ,[QueN1,...,QueNN] ]    */
179/* where Queij is 1 if the the  is a queen on the ith line an jth row.     */
180/*                                                                         */
181/* Solution:                                                               */
182/* N=4  [[0,0,1,0],         [[0,1,0,0],                                    */
183/*       [1,0,0,0],          [0,0,0,1],                                    */
184/*       [0,0,0,1],  and     [1,0,0,0],                                    */
185/*       [0,1,0,0]]          [0,0,1,0]]                                    */
186/*                                                                         */
187/* N=8  [[0,0,0,0,0,0,0,1], (first solution)                               */
188/*       [0,0,0,1,0,0,0,0],                                                */
189/*       [1,0,0,0,0,0,0,0],                                                */
190/*       [0,0,1,0,0,0,0,0],                                                */
191/*       [0,0,0,0,0,1,0,0],                                                */
192/*       [0,1,0,0,0,0,0,0],                                                */
193/*       [0,0,0,0,0,0,1,0],                                                */
194/*       [0,0,0,0,1,0,0,0]]                                                */
195/*-------------------------------------------------------------------------*/
196
197
198bqueens:-	write('N ?'), read(N),
199	Starttime is cputime,
200	(bqueens(N,A),
201%        write(A), nl,
202	 fail
203	   ;
204	 write('No more solutions'), nl),
205	Y is cputime-Starttime,
206	write('time : '), write(Y), nl.
207
208
209
210
211bqueens(N,A):-
212	create_array(N,N,A),
213	for_each_line(A,only1),
214	for_each_column(A,only1),
215	for_each_diagonal(A,N,N,atmost1),
216	!,
217	array_labeling(A).
218
219
220
221
222
223
224
225
226%--- b_bips.pl ---
227
228
229
230%I also use the following shorthands:
231
232and0(X,Y):-
233	and(X,Y,0).
234%	delay([X,Y],and(X,Y,0)).
235
236
237
238or1(X,Y):-
239	or(X,Y,1).
240
241
242and0(X,Y,Z):-
243	and(X,Y,XY),
244	and(XY,Z,0).
245%	delay([X,Y,Z],(
246%	and(X,Y,XY),
247%	and(XY,Z,0))).
248
249
250
251
252or1(X,Y,Z):-
253	or(X,Y,XY),
254	or(XY,Z,1).
255
256
257/*-------------------------------------------------------------------------*/
258/* Prolog to Wam Compiler               INRIA Rocquencourt - ChLoE Project */
259/* Version 1.0  -  C Run-time                           Daniel Diaz - 1991 */
260/* Extended to FD Constraints (July 1992)                                  */
261/*                                                                         */
262/* Built-In: B predicates (booleans)                                       */
263/*                                                                         */
264/* b_bips.pl                                                               */
265/*-------------------------------------------------------------------------*/
266
267	/* Symbolic constraints */
268
269%:- public only_one/1, at_least_one/1, at_most_one/1.
270
271%only_one(L):- card(1,1,L).
272%at_most_one(L):- card(0,1,L).
273
274
275only_one(L):-
276	at_least_one(L),
277	at_most_one(L).
278
279
280
281
282at_least_one(L):-
283	at_least_one1(L,1).
284
285
286at_least_one1([X],X).
287
288at_least_one1([X|L],R):-
289	at_least_one1(L,R1),
290	or(X,R1,R).
291
292
293
294
295at_most_one([]).
296
297at_most_one([X|L]):-
298	not_two(L,X),
299	at_most_one(L).
300
301
302
303
304not_two([],_).
305
306not_two([X1|L],X):-
307	and0(X1,X),
308	not_two(L,X).
309
310
311
312	/* Array procedures */
313
314%:- public create_array/3, for_each_line/2, for_each_column/2, for_each_diagonal/4, array_labeling/1.
315
316
317	/*---------------------------------------------------------*/
318	/*                                                         */
319	/* An array NL x NC elements is represented as follows :   */
320	/* A = [L_1, ..., L_NL] with L_i = [X_i_1, ..., X_i_NC]    */
321	/* Hence :                                                 */
322	/* A = [ [X_1_1,..., X_1_NC], ..., [X_NL_1,..., X_NL_NC] ] */
323	/*---------------------------------------------------------*/
324
325	% create_array(NL,NC,A)
326	%     NL: nb of lines   NC:nb of columns   A:array
327	%     creates an array (with unbound variables)
328
329create_array(NL,NC,A):-
330	create_array1(0,NL,NC,A),
331	!.
332
333
334create_array1(NL,NL,_,[]).
335
336create_array1(I,NL,NC,[L|A]):-
337	create_one_line(0,NC,L),
338	I1 is I+1,
339	create_array1(I1,NL,NC,A).
340
341
342
343
344create_one_line(NC,NC,[]).
345
346create_one_line(J,NC,[_|L]):-
347	J1 is J+1,
348	create_one_line(J1,NC,L).
349
350
351
352
353	% for_each_line(A,P)
354	%     A:array   P: program atom
355	%     calls: array_prog(P,L) for each line L (L is a list)
356
357for_each_line([],_).
358
359for_each_line([L|A],P):-
360	array_prog(P,L),
361	for_each_line(A,P).
362
363
364
365
366	% for_each_column(A,P)
367	%     A:array   P: program atom
368	%     calls:  array_prog(P,L) for each column L (L is a list)
369
370for_each_column([[]|_],_):-
371	!.
372
373for_each_column(A,P):-
374	create_column(A,C,A1),
375	array_prog(P,C),
376	for_each_column(A1,P).
377
378
379
380
381create_column([],[],[]).
382
383create_column([[X|L]|A],[X|C],[L|A1]):-
384	create_column(A,C,A1).
385
386
387
388
389	% for_each_diagonal(A,NL,NC,P)
390	%     A:array   NL: nb of lines
391	%     NC:nb of columns   P: program atom
392	%     calls:  array_prog(P,L) for each diagonal D (D is a list)
393
394for_each_diagonal(A,NL,NC,P):-
395	NbDiag is 2*(NL+NC-1),              % numbered from 0 to NbDiag-1
396	create_lst_diagonal(0,NbDiag,LD),
397	fill_lst_diagonal(A,0,NL,NC,LD,LD1),
398	!,
399	for_each_line(LD1,P).
400
401
402
403
404create_lst_diagonal(NbDiag,NbDiag,[]).
405
406create_lst_diagonal(I,NbDiag,[[]|LD]):-
407	I1 is I+1,
408	create_lst_diagonal(I1,NbDiag,LD).
409
410
411
412
413fill_lst_diagonal([],_,_,_,LD,LD).
414
415fill_lst_diagonal([L|A],I,NL,NC,LD,LD2):-
416	I1 is I+1,
417	fill_lst_diagonal(A,I1,NL,NC,LD,LD1),
418	one_list(L,I,NL,0,NC,LD1,LD2).
419
420
421
422
423
424one_list([],_,_,_,_,LD,LD).
425
426one_list([X|L],I,NL,J,NC,LD,LD3):-
427	J1 is J+1,
428	one_list(L,I,NL,J1,NC,LD,LD1),
429	NoDiag1 is I+J,
430	NoDiag2 is I+NC-J+NL+NC-2,
431	add_in_lst_diagonal(0,NoDiag1,X,LD1,LD2),
432	add_in_lst_diagonal(0,NoDiag2,X,LD2,LD3).
433
434
435
436
437
438add_in_lst_diagonal(NoDiag,NoDiag,X,[D|LD],[[X|D]|LD]).
439
440add_in_lst_diagonal(K,NoDiag,X,[D|LD],[D|LD1]):-
441	K1 is K+1,
442	add_in_lst_diagonal(K1,NoDiag,X,LD,LD1).
443
444
445
446array_prog(only1,L):- !,
447	only_one(L).
448
449array_prog(atmost1,L):- !,
450	at_most_one(L).
451
452
453
454
455array_labeling([]).
456
457array_labeling([L|A]):-
458	label_bool(L),
459	array_labeling(A).
460
461
462%--- end ---
463