fd_exactly/3

Niech X1, X2, ..., Xm będą FD-zmiennymi. Chcemy na zmienne te narzucić warunek, że dokładnie N z nich ma wartość równą K, gdzie N i K są liczbami całkowitymi.

W tym celu możemy użyć w GNU-Prologu predykatu fd_exactly/3, którego pierwszym argumentem jest N, drugim lista zmiennych [X1, X2, ..., Xm] a trzecim wartość K.

Oto prosty przykład, w którym trzy spośród czterech zmiennych o dziedzinach 0..3 ma wartość 1:

| ?- X = [X1, X2, X3, X4], fd_domain(X, 0, 3), fd_exactly(3, X, 1).

X = [_#3(0..3),_#25(0..3),_#47(0..3),_#69(0..3)]
X1 = _#3(0..3)
X2 = _#25(0..3)
X3 = _#47(0..3)
X4 = _#69(0..3)

yes

Jeśli dodatkowo na zmienną X2 narzucimy warunek, że jest ona większa od 1, to system wywnioskuje, że pozostałe zmienne muszą mieć wartość 1:

| ?- X = [X1, X2, X3, X4], fd_domain(X, 0, 3), fd_exactly(3, X, 1), X2 #> 1.

X = [1,_#25(2..3),1,1]
X1 = 1
X2 = _#25(2..3)
X3 = 1
X4 = 1

yes

Częstym błędem jest użycie predykatu fd_exactly/3 z FD-zmienną N lub K zamiast konkretną liczbą całkowitą.

Spróbujmy na cztery zmienne o dziedzinach 0..2 narzucić warunek, że wartość 2 występuje wśród nich o jeden raz więcej niż wartość 1:

| ?- X = [X1, X2, X3, X4], fd_domain(X, 0, 2),
     fd_exactly(N1, X, 1), fd_exactly(N2, X, 2), N2 #= N1+1.
uncaught exception: error(instantiation_error,fd_exactly/3)

Zgłoszony wyjątek sygnalizuje, że jeden z argumentów predykatu fd_exactly/3 jest niepoprawnej postaci.

Aby obejść ograniczenia predykatu fd_exactly/3 można zdefiniować własną jego wersję, która buduje listę odpowiednich równań i za pomocą predykatu fd_cardinality/2 narzuca warunek, że dokładnie N z nich jest spełnionych.

my_exactly(N, X, K) :-
     rownania(X, K, R),
     fd_cardinality(R, N).

rownania([], _, []).
rownania([Xi | L1], K, [Xi #= K | L2]) :-
     rownania(L1, K, L2).

Tym razem udaje się narzucić wszystkie warunki:

| ?- X = [X1, X2, X3, X4], fd_domain(X, 0, 2),
     my_exactly(N1, X, 1), my_exactly(N2, X, 2), N2 #= N1+1.

N1 = _#91(0..3)
N2 = _#339(1..4)
X = [_#3(0..2),_#25(0..2),_#47(0..2),_#69(0..2)]
X1 = _#3(0..2)
X2 = _#25(0..2)
X3 = _#47(0..2)
X4 = _#69(0..2)

yes

O tym, że warunki zostały dobrze narzucone można przekonać się drukując wszystkie rozwiązania:

| ?- X = [X1, X2, X3, X4], fd_domain(X, 0, 2),
     my_exactly(N1, X, 1), my_exactly(N2, X, 2), N2 #= N1+1,
     fd_labeling(X), write(X), nl, fail.
[0,0,0,2]
[0,0,2,0]
[0,1,2,2]
[0,2,0,0]
[0,2,1,2]
[0,2,2,1]
[1,0,2,2]
[1,2,0,2]
[1,2,2,0]
[2,0,0,0]
[2,0,1,2]
[2,0,2,1]
[2,1,0,2]
[2,1,2,0]
[2,2,0,1]
[2,2,1,0]

no

Użyty w powyższym przykładzie predykat fd_labeling/1 znajduje wartości zmiennych spełniające wszystkie narzucone warunki, natomiast przy nawrotach spowodowanych predykatem fail/0, znajdowane są kolejne odpowiedzi.

Tags: gnu-prolog