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
Then, the magic sequence solver is loaded:
| ?- consult(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
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
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
Please note: the call tolength/2is necessary; otherwise,Lwould 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
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.