Use reified constraints to make 3 numbers consecutive

Question

Here's an outline of my SWI-Prolog program:

:- use_module(library(clpfd)).

consec1(L) :-
   L=[L1,L2,L3,L4,L5,L6,L7,L8,L9],
   L ins 1..9,
   ...,
   abs(L5-L4)#=1,
   all_different(L),
   labeling([],L)

abs(L5-L4)#=1 makes L5 and L4 next to each other. If I wanted to make three numbers next to each other e.g. L3, L4 and L5, how could I use reified constraints to do this?

E.g. L3=4,L5=5,L4=6 or L4=7,L5=8,L3=9

With 'consecutive', do you mean e.g. `(L2#=L1+1 #/\ L3#=L2+1) #\/ (L2#=L1-1 #/\ L3#=L2-1)`? — repeat, May 08 '15 at 05:00
Also, should that relation hold for all 3 adjacent members of L---or just for some/any? — repeat, May 08 '15 at 05:02

score 3 · Accepted Answer · edited Dec 16 '15 at 19:05

This implements consecutive in the sense you gave in the comments. For a list of N values, we need space enough to make all the values fit in between, and all values need to be different.

consecutive([]).  % debatable case
consecutive(Xs) :-
   Xs = [_|_],
   length(Xs, N),
   all_different(Xs),
   max_of(Max, Xs),
   min_of(Min, Xs),
   Max-Min #= N-1.

max_of(Max, [Max]).
max_of(Max0, [E|Es]) :-
   Max0 #= max(E,Max1),
   max_of(Max1, Es).

min_of(Min, [Min]).
min_of(Min0, [E|Es]) :-
   Min0 #= min(E, Min1),
   min_of(Min1, Es).

score 2 · Answer 2 · edited May 23 '17 at 12:15

TL;DR: too long for a comment: play-time with specialized sicstus-prolog clpfd constraints

This answer follows up this previous answer; recent versions of SICStus Prolog offer specialized clpfd constraints maximum/2 and minimum/2 as alternatives to min_of/2 and max_of/2.

Using the following code for benchmarking^1,2 ...

:- use_module(library(clpfd)).
:- use_module(library(between)).

bench_(How, N, Ub) :-
   \+ \+ ( length(Xs, N),
           domain(Xs, 1, Ub),
           all_different(Xs),
           Max-Min #= N-1,
           (  How = 0
           ;  How = min_of , max_of( Max, Xs), min_of( Min, Xs)
           ;  How = minimum, maximum(Max, Xs), minimum(Min, Xs)
           ),
           labeling([enum], Xs) ).

... we run the following tests:

To estimate worst-case overhead of min/max constraint:

?- member(How, [0,v1,v2]), call_time(bench_(How,10,10), T_ms).
   How = 0 , T_ms =  5910
;  How = v1, T_ms = 19560
;  How = v2, T_ms =  7190.

To measure the runtime costs of propagating min/max constraints in more typical cases:

?- between(6, 8, N), NN #= N+N, call_time(bench_(v1,N,NN),T_ms).
   N = 6, NN = 12, T_ms =   50 
;  N = 7, NN = 14, T_ms =  300
;  N = 8, NN = 16, T_ms = 2790.

?- between(6, 8, N), NN #= N+N, call_time(bench_(v2,N,NN),T_ms).
   N = 6, NN = 12, T_ms =   20
;  N = 7, NN = 14, T_ms =  100
;  N = 8, NN = 16, T_ms =  830.

In both "use cases", the specialized constraints give impressive speedup.

^{Footnote 1: Using SICStus Prolog version 4.3.2 (64-bit).

Footnote 2: Answer sequences were post-processed to improve appearance.}

Use reified constraints to make 3 numbers consecutive

2 Answers2