The problem of magic sequences is a well known constraint problem. A magic sequence is a list, where the i-th item of the list is equal to the number of occurrences of the number i in the list, starting from zero. For example, the following is a magic sequence:
[1,2,1,0]
The CLP(FD) solution can be found in
library('clpfd/examples/magicseq'), which provides a couple of
different solutions, one of which uses the global_cardinality/2
constraint. We'll use this solution to demonstrate a simple session
with FDBG.
First, the debugger is imported into the user module:
| ?- use_module(fdbg).
% loading /home/matsc/sicstus3/Utils/x86-linux-glibc2.2/lib/sicstus-3.9.1/library/fdbg.po...
% module fdbg imported into user
[...]
% loaded /home/matsc/sicstus3/Utils/x86-linux-glibc2.2/lib/sicstus-3.9.1/library/fdbg.po in module fdbg, 220 msec 453936 bytes
yes
Then, the magic sequence solver is loaded:
| ?- [library('clpfd/examples/magicseq')].
% consulting /home/matsc/sicstus3/Utils/x86-linux-glibc2.2/lib/sicstus-3.9.1/library/clpfd/examples/magicseq.pl...
% module magic imported into user
% module clpfd imported into magic
% consulted /home/matsc/sicstus3/Utils/x86-linux-glibc2.2/lib/sicstus-3.9.1/library/clpfd/examples/magicseq.pl in module magic, 30 msec 9440 bytes
yes
Now we turn on the debugger, telling it to save the trace in fdbg.log.
| ?- fdbg_on([file('fdbg.log',write)]).
% The clp(fd) debugger is switched on
yes
To produce a well readable trace output, a name has to be assigned to the list representing the magic sequence. To avoid any modifications to the source code, the name is assigned by a separate call before calling the magic sequence finder predicate:
| ?- length(L,4), fdbg_assign_name(L,list), magic_gcc(4,L,[enum]).
L = [1,2,1,0] ? ;
L = [2,0,2,0] ? ;
no
(NOTE: the call to length/2 is necessary; otherwise, L would
be a single variable instead of a list of four variables when the name
is assigned.)
Finally we turn the debugger off:
| ?- fdbg_off.
% The clp(fd) debugger is switched off
yes
The output of the sample run can be found in fdbg.log. Here, we
show selected parts of the trace. In each block, the woken constraint
appears on the first line, followed by the corresponding legend.
In the first displayed block, scalar_product/4 removes infeasible
domain values from list_3 and list_4, thus adjusting their
upper bounds. The legend shows the domains before and after pruning.
Note also that the constraint is rewritten to a more readable form:
<list_2>+2*<list_3>+3*<list_4>#=4
list_2 = 0..3
list_3 = 0..3 -> 0..2
list_4 = 0..3 -> 0..1
The following block shows the initial labeling events,
trying the value 0 for list_1:
Labeling [22, <list_1>]: starting in range 0..3.
Labeling [22, <list_1>]: indomain_up: <list_1> = 0
This immediately leads to a dead end:
global_cardinality([0,<list_2>,<list_3>,<list_4>],
[0-0,1-<list_2>,2-<list_3>,3-<list_4>])
list_2 = 0..3
list_3 = 0..2
list_4 = 0..1
Constraint failed.
We backtrack on list_1, trying instead the value 1.
This leads to the following propagation steps:
Labeling [22, <list_1>]: indomain_up: <list_1> = 1
global_cardinality([1,<list_2>,<list_3>,<list_4>],
[0-1,1-<list_2>,2-<list_3>,3-<list_4>])
list_2 = 0..3 -> 1..3
list_3 = 0..2
list_4 = 0..1
<list_2>+2*<list_3>+3*<list_4>#=4
list_2 = 1..3
list_3 = 0..2 -> 0..1
list_4 = 0..1
However, we do not yet have a solution, so we try the
first feasible value for list_2, which is 2.
This is in fact enough to solve the goal.
In the last two propagation steps, the constraint exits, which means
that it holds no matter what value any remaining variable takes
(in this example, there are none):
Labeling [29, <list_2>]: indomain_up: <list_2> = 2
global_cardinality([1,2,<list_3>,<list_4>],[0-1,1-2,2-<list_3>,3-<list_4>])
list_3 = 0..1 -> {1}
list_4 = 0..1 -> {0}
global_cardinality([1,2,1,0],[0-1,1-2,2-1,3-0])
Constraint exited.
0#=0
Constraint exited.