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