1/* 2 examplesFLOPS2024.pl 3 4 @author Francois Fages 5 @email Francois.Fages@inria.fr 6 @institute Inria, France 7 @license LGPL-2 8 9 @version 1.1.3 10 11 12 13*/ 14 15:- module(examplesFLOPS2024, 16 [ 17 queens/2, 18 queens_distinct/2, 19 queens_sym/2, 20 sym_elim/2, 21 queens_sym_distinct/2, 22 23 queens_list/2, 24 queens_distinct_list/2, 25 queens_sym_list/2, 26 sym_elim_list/2, 27 queens_sym_distinct_list/2, 28 29 show/1, 30 31 fourier/4, 32 33 benchmark/0 34 ]).

Examples of models presented at FLOPS 2024 to show the absence of computational overhead

author

- Francois Fages

version

- 1.1.3

Examples of use of SWI-Prolog pack modeling published in

F. Fages. A Constraint-based Mathematical Modeling Library in Prolog with Answer Constraint Semantics. 17th International Symposium on Functional and Logic Programming, FLOPS 2024. May 15, 2024 - May 17, 2024, Kumamoto, Japan. LNCS, Springer-Verlag.

Generation of constraints by comprehension on subscripted variables, in the spirit of MiniZinc modeling language:

queens(N, Queens):-
  int_array(Queens, [N], 1..N),
  for_all([I in 1..N-1, D in 1..N-I],
          (Queens[I] #\= Queens[I+D],
           Queens[I] #\= Queens[I+D]+D,
           Queens[I] #\= Queens[I+D]-D)),
  satisfy(Queens).

show_array(Queens):-
    array(Queens, [N]),
    for_all([I, J] in 1..N,
            let([QJ = Queens[J],
                 Q = if(QJ = I, 'Q', '.'),
                 B = if(J = N, '\n', ' ')],
                format("~w~w",[Q,B]))),
    nl.

?- queens(8,Queens), show_array(Queens).
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. Q . . . . . .
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .

Queens = array(1, 5, 8, 6, 3, 7, 2, 4) .

For some reason the computation times in SWI-prolog 9.2.6 seem 30% higher than in version 9.2.2 but still with no significant difference between the use of arrays or lists in these examples.

?- benchmark.
queens(100,_3382172)
% 4,536,855 inferences, 0.422 CPU in 0.491 seconds (86% CPU, 10754180 Lips)
queens_list(100,_5922054)
% 4,483,345 inferences, 0.422 CPU in 0.484 seconds (87% CPU, 10633742 Lips)
queens_distinct(100,_6780512)
% 64,402,829 inferences, 4.425 CPU in 4.848 seconds (91% CPU, 14553427 Lips)
queens_distinct_list(100,_2521402)
% 64,375,035 inferences, 4.359 CPU in 4.765 seconds (91% CPU, 14769059 Lips)
queens(8,_2681598),fail
% 763,684 inferences, 0.057 CPU in 0.065 seconds (88% CPU, 13352053 Lips)
queens_list(8,_2682252),fail
% 763,075 inferences, 0.063 CPU in 0.072 seconds (88% CPU, 12065381 Lips)
queens_distinct(8,_2682906),fail
% 4,220,968 inferences, 0.436 CPU in 0.493 seconds (88% CPU, 9686607 Lips)
queens_distinct_list(8,_8578),fail
% 4,218,651 inferences, 0.386 CPU in 0.438 seconds (88% CPU, 10931781 Lips)
queens_sym(8,_8496),fail
% 674,986 inferences, 0.062 CPU in 0.073 seconds (85% CPU, 10862693 Lips)
queens_sym_list(8,_9150),fail
% 670,198 inferences, 0.063 CPU in 0.073 seconds (87% CPU, 10623225 Lips)
queens_sym_distinct(8,_143930),fail
% 1,518,491 inferences, 0.151 CPU in 0.174 seconds (87% CPU, 10060163 Lips)
queens_sym_distinct_list(8,_33578),fail
% 1,565,125 inferences, 0.147 CPU in 0.167 seconds (88% CPU, 10642186 Lips)
fourier(2,_24502,_24504,1)
% 2,821 inferences, 0.001 CPU in 0.001 seconds (81% CPU, 3374402 Lips)
true.

Symbolic answer constraints not only ground solutions:

fourier(P, X, Y, F):-
    float_array(Force_Leg, [3], 0..F),
    {Force_Leg[1]+Force_Leg[2]+Force_Leg[3] = P,
     X*P = 20*Force_Leg[2],
     Y*P = 20*Force_Leg[3]}.

?- fourier(3, X, Y, 1).
X = Y, Y = 6.666666666666667.

?- fourier(3.1, X, Y, 1).
false.

?- fourier(2, X, Y, 1).
{Y=20.0-10.0*_A-10.0*_B, X=10.0*_B, _=2.0-_A-_B, _A+_B>=1.0, _B=<1.0, _A=<1.0}.

132:- reexport(library(modeling)). 133 134 % N-QUEENS PLACEMENT MODELS USING SUBSCRIPTED VARIABLES 135 136 137%! queens(+N, ?Queens) 138% 139% solves the N Queens problems using arrays. 140 141queens(N, Queens):- 142 int_array(Queens, [N], 1..N), 143 for_all([I in 1..N-1, D in 1..N-I], 144 (Queens[I] #\= Queens[I+D], 145 Queens[I] #\= Queens[I+D]+D, 146 Queens[I] #\= Queens[I+D]-D)), 147 satisfy(Queens). 148 149 150 151%! queens_distinct(+N, ?Queens) 152% 153% solves the N Queens problems using arrays and the global constraint all_distinct/1 of library(clpfd) 154 155queens_distinct(N, Queens):- 156 int_array(Queens, [N], 1..N), 157 158 int_array(Indices, [N]), 159 for_all(I in 1..N, cell(Indices, I, I)), 160 161 op_rel(Queens, +, Indices, #=, QueensPlusI), 162 op_rel(Queens, -, Indices, #=, QueensMinusI), 163 164 all_distinct(QueensPlusI), 165 all_distinct(Queens), 166 all_distinct(QueensMinusI), 167 168 satisfy(Queens). 169 170 171%! queens_sym(+N, ?Queens) 172% 173% solves the N Queens problems with symmetry breaking using arrays. 174 175queens_sym(N, Queens):- 176 int_array(Queens, [N], 1..N), 177 for_all([I in 1..N-1, D in 1..N-I], 178 (Queens[I] #\= Queens[I+D], 179 Queens[I] #\= Queens[I+D]+D, 180 Queens[I] #\= Queens[I+D]-D)), 181 sym_elim(N, Queens), 182 satisfy(Queens). 183 184 185%! sym_elim(+N, ?Queens) 186% 187% introduces symmetrical array models and posts lex_leq/2 constraints to eliminate symmetries. 188 189sym_elim(N, Queens) :- 190 191 Queens[1] #< Queens[N], % vertical reflection 192 Queens[1] #=< (N+1)//2, % horizontal reflection 193 194 int_array(Dual, [N], 1..N), 195 for_all([I, J] in 1..N, Queens[I] #= J #<==> Dual[J] #= I), 196 lex_leq(Queens, Dual), % first diagonal reflection 197 198 int_array(SecondDiagonal, [N], 1..N), 199 for_all(I in 1..N, SecondDiagonal[I] #= N + 1 - Dual[N+1-I]), 200 lex_leq(Queens, SecondDiagonal), 201 202 int_array(R90, [N], 1..N), 203 for_all(I in 1..N, R90[I] #= Dual[N+1-I]), 204 lex_leq(Queens, R90), % rotation 90Â° 205 206 int_array(R180, [N], 1..N), 207 for_all(I in 1..N, R180[I] #= N + 1 - Queens[N+1-I]), 208 lex_leq(Queens, R180), 209 210 int_array(R270, [N], 1..N), 211 for_all(I in 1..N, R270[I] #= N + 1 - Dual[I]), 212 lex_leq(Queens, R270). 213 214 215 216%! queens_sym_distinct(+N, ?Queens) 217% 218% solves the N Queens problems with symmetry breaking using arrays and global constraint all_distinct/1. 219 220queens_sym_distinct(N, Queens):- 221 int_array(Queens, [N], 1..N), 222 int_array(Indices, [N]), 223 for_all(I in 1..N, cell(Indices, I, I)), 224 op_rel(Queens, +, Indices, #=, QueensPlusI), 225 op_rel(Queens, -, Indices, #=, QueensMinusI), 226 all_distinct(QueensPlusI), 227 all_distinct(Queens), 228 all_distinct(QueensMinusI), 229 230 sym_elim(N, Queens), 231 232 satisfy(Queens). 233 234 235 % N-QUEENS PLACEMENT PROGRAMS USING LISTS 236 237 238%! queens_list(+N, ?Queens) 239% 240% standard program using lists for the N Queens problem. 241 242queens_list(N, Queens):- 243 length(Queens, N), 244 Queens ins 1..N, 245 safe(Queens), 246 labeling([ff], Queens). 247 248safe([]). 249safe([QI | Tail]) :- 250 noattack(Tail, QI, 1), 251 safe(Tail). 252 253noattack([], _, _). 254noattack([QJ | Tail], QI, D) :- 255 QI #\= QJ, 256 QI #\= QJ + D, 257 QI #\= QJ - D, 258 D1 #= D + 1, 259 noattack(Tail, QI, D1). 260 261 262%! queens_distinct_list(+N, ?Queens) 263% 264% program using lists and the global constraint all_distinct/1 of library(clpfd) 265 266queens_distinct_list(N, Queens):- 267 length(Queens, N), 268 Queens ins 1..N, 269 270 length(Indices, N), 271 for_all(I in 1..N, nth1(I, Indices, I)), 272 273 op_rel(Queens, +, Indices, #=, QueensPlusI), 274 op_rel(Queens, -, Indices, #=, QueensMinusI), 275 276 all_distinct(QueensPlusI), 277 all_distinct(Queens), 278 all_distinct(QueensMinusI), 279 280 labeling([ff], Queens). 281 282 283%! queens_sym_list(+N, ?Queens) 284% 285% list program to break symmetries in the N Queens problem. 286 287queens_sym_list(N, Queens) :- 288 length(Queens, N), 289 Queens ins 1..N, 290 safe(Queens), 291 292 sym_elim_list(N, Queens), 293 294 labeling([ff], Queens). 295 296 297%! sym_elim_list(+N, ?Queens) 298% 299% introduces symmetrical list models and posts lex_leq/2 constraints to eliminate symmetries. 300 301sym_elim_list(N, Queens) :- 302 last(Queens, Last), 303 Queens = [First | _], 304 First #< Last, 305 First #=< (N+1) // 2, 306 307 dual(N, Queens, Dual), 308 lex_leq(Queens, Dual), 309 310 length(CounterDiagonal, N), 311 reverse(Dual, DualReversed), % in order N+1-I 312 counterdiag(CounterDiagonal, 1, N, DualReversed), 313 lex_leq(Queens, CounterDiagonal), 314 315 length(R90, N), 316 r90(R90, 1, N, DualReversed), 317 lex_leq(Queens, R90), 318 319 length(R180, N), 320 reverse(Queens, QueensReversed), % in order N+1-I 321 r180(R180, 1, N, QueensReversed), 322 lex_leq(Queens, R180), 323 324 length(R270, N), 325 r180(R270, 1, N, Dual), % not a typo ! since applied here to the dual instead of the reversed primal 326 lex_leq(Queens, R270). 327 328 329dual(N, Queens, Dual):- 330 length(Dual, N), 331 forall_IJ(Queens, 1, Dual). 332 333forall_IJ([], _, _). 334forall_IJ([QI |Qs], I, Dual):- 335 forall_J(Dual, 1, QI, I), 336 I1 #= I+1, 337 forall_IJ(Qs, I1, Dual). 338 339forall_J([], _, _, _). 340forall_J([RJ | R], J, QI, I):- 341 (QI#=J) #<==> (RJ#=I), 342 J1 #= J+1, 343 forall_J(R, J1, QI, I). 344 345counterdiag([], _, _, _). 346counterdiag([CI | CounterDiagonal], I, N, [DI | Dual]):- 347 CI #= N+1-DI, 348 I1 is I+1, 349 counterdiag(CounterDiagonal, I1, N, Dual). 350 351r90([], _, _, _). 352r90([RI | R90], I, N, [DI | Dual]):- 353 RI #= DI, 354 I1 is I+1, 355 r90(R90, I1, N, Dual). 356 357r180([], _, _, _). 358r180([RI | R90], I, N, [DI | Dual]):- 359 RI #= N+1-DI, 360 I1 is I+1, 361 r180(R90, I1, N, Dual). 362 363 364%! queens_sym_distinct_list(+N, ?Queens) 365% 366% list program with symmetry breaking and global constraint all_distinct/1 367 368queens_sym_distinct_list(N, Queens) :- 369 length(Queens, N), 370 Queens ins 1..N, 371 372 length(Indices, N), 373 for_all(I in 1..N, nth1(I, Indices, I)), 374 375 op_rel(Queens, +, Indices, #=, QueensPlusI), 376 op_rel(Queens, -, Indices, #=, QueensMinusI), 377 378 all_distinct(QueensPlusI), 379 all_distinct(Queens), 380 all_distinct(QueensMinusI), 381 382 sym_elim_list(N, Queens), 383 384 labeling([ff], Queens). 385 386 387 % PRETTY-PRINT OF THE CHESSBOARD PLACEMENT

394show(Queens):- 395 (array(Queens) 396 -> 397 show_array(Queens) 398 ; 399 show_list(Queens)). 400 401show_array(Queens):- 402 array(Queens, [N]), 403 for_all([I, J] in 1..N, 404 let([QJ = Queens[J], 405 Q = if(QJ = I, 'Q', '.'), 406 B = if(J = N, '\n', ' ')], 407 format("~w~w",[Q,B]))), 408 nl. 409 410show_list(Queens):- 411 length(Queens, N), 412 for_all([I, J] in 1..N, 413 exists(QJ, 414 (nth1(J, Queens, QJ), 415 let([Q = if(QJ = I, 'Q', '.'), 416 B = if(J = N, '\n', ' ')], 417 format("~w~w",[Q,B]))))), 418 nl. 419 420 421 % BENCHMARKING v9.2.2 422/* 423 ?- benchmark. 424user:queens(100,_69028) 425% 4,552,518 inferences, 0.373 CPU in 0.387 seconds (96% CPU, 12212181 Lips) 426user:queens_list(100,_2790392) 427% 4,472,406 inferences, 0.298 CPU in 0.310 seconds (96% CPU, 15025469 Lips) 428user:queens_distinct(100,_8210576) 429% 63,565,626 inferences, 3.611 CPU in 3.641 seconds (99% CPU, 17603740 Lips) 430user:queens_distinct_list(100,_1467832) 431% 63,502,308 inferences, 3.470 CPU in 3.484 seconds (100% CPU, 18298489 Lips) 432user:(queens(8,_1913650),fail) 433% 757,835 inferences, 0.041 CPU in 0.041 seconds (99% CPU, 18435668 Lips) 434user:(queens_list(8,_1914304),fail) 435% 757,303 inferences, 0.042 CPU in 0.043 seconds (99% CPU, 17926877 Lips) 436user:(queens_distinct(8,_1914958),fail) 437% 4,025,643 inferences, 0.297 CPU in 0.303 seconds (98% CPU, 13541040 Lips) 438user:(queens_distinct_list(8,_79224),fail) 439% 4,012,622 inferences, 0.289 CPU in 0.295 seconds (98% CPU, 13908424 Lips) 440user:(queens_sym(8,_33346),fail) 441% 667,850 inferences, 0.045 CPU in 0.046 seconds (98% CPU, 14860595 Lips) 442user:(queens_sym_list(8,_34000),fail) 443% 664,708 inferences, 0.048 CPU in 0.049 seconds (97% CPU, 13812975 Lips) 444user:(queens_sym_distinct(8,_34654),fail) 445% 1,471,542 inferences, 0.125 CPU in 0.132 seconds (95% CPU, 11760763 Lips) 446user:(queens_sym_distinct_list(8,_34510),fail) 447% 1,509,989 inferences, 0.128 CPU in 0.132 seconds (97% CPU, 11818117 Lips) 448true. 449*/ 450 451:- set_prolog_flag(optimise, true).

456benchmark :- 457 queens(100, _), !, % added in version 1.1.3 for compiling before testing 458 % first solution 459 test(queens(100, _)), 460 test(queens_list(100, _)), 461 test(queens_distinct(100, _)), 462 test(queens_distinct_list(100, _)), 463 % all solutions 464 test((queens(8, _), fail)), 465 test((queens_list(8, _), fail)), 466 test((queens_distinct(8, _), fail)), 467 test((queens_distinct_list(8, _), fail)), 468 % non symmetrical solutions 469 test((queens_sym(8, _), fail)), 470 test((queens_sym_list(8, _), fail)), 471 test((queens_sym_distinct(8, _), fail)), 472 test((queens_sym_distinct_list(8, _), fail)), 473 % clpr interface 474 test(fourier(2, _, _, 1)). 475 476 477test(Goal):- 478 writeln(Goal), 479 (time(Goal) -> true ; true). 480 481 482 483 484 % FOURIER'S EXAMPLE OVER THE REAL NUMBERS 485 486 487%! fourier(?P, ?X, ?Y, ?F) 488% 489% Placing a weight P at coordinates X Y on an isocel triangle table with 3 legs at coordinates (0,0), (20, 0) and (0, 20) 490% and with a maximum force F exerted on each leg. 491 492fourier(P, X, Y, F):- 493 float_array(Force_Leg, [3], 0