Previous: FDBG Annotation, Up: FDBG Basics [Contents][Index]
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(library(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 | ?- use_module(library(clpfd)). […]
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
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_demo(4,L). L = [1,2,1,0] ? ; L = [2,0,2,0] ? ; no
Please 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
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 selected block, scalar_product/4
removes infeasible
domain values from list_4
, adjusting its upper bound. 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>#=<list_1>+<list_2>+<list_3>+<list_4> list_1 = 0..3 list_2 = 0..3 list_3 = 0..3 list_4 = 0..3 -> 0..1
The following block shows the initial labeling events,
trying the value 0 for list_1
:
Labeling [9, <list_1>]: starting in range 0..3. Labeling [9, <list_1>]: indomain_up: <list_1> = 0
This soon leads to a dead end:
<list_1>=0 list_1 = 0..3 -> {0} Constraint exited. <list_2>+2*<list_3>+3*<list_4>#=<list_2>+<list_3>+<list_4> list_2 = 0..3 list_3 = 0..3 -> {0} list_4 = 0..1 -> {0} Constraint exited. <list_2>+<list_3>+<list_4>#=4 list_2 = 0..3 list_3 = {0} list_4 = {0} Constraint failed.
We backtrack on list_1
, trying instead the value 1. This leads
to the following propagation steps and to the first solution. In these
propagation steps, the constraint exits, which means that it holds no
matter what value any remaining variable takes (like list_2
in the second step):
Labeling [9, <list_1>]: indomain_up: <list_1> = 1 <list_1>=1 list_1 = 0..3 -> {1} Constraint exited. <list_2>+2*<list_3>+3*<list_4>#=1+<list_2>+<list_3>+<list_4> list_2 = 0..3 list_3 = 0..3 -> {1} list_4 = 0..1 -> {0} Constraint exited. 1+<list_2>+<list_3>+<list_4>#=4 list_2 = 0..3 -> {2} list_3 = {1} list_4 = {0} Constraint exited. global_cardinality([1,<list_2>,<list_3>,<list_4>],[0-1,1-<list_2>,2-<list_3>,3-<list_4>],[consistency(domain)]) list_2 = {2} list_3 = {1} list_4 = {0} Constraint exited.
Then, we backtrack again on list_1
, which leads to the second
solution after a chain of propagation steps:
Labeling [9, <list_1>]: indomain_up: <list_1> = 2 [...] global_cardinality([2,<list_2>,<list_3>,<list_4>],[0-2,1-<list_2>,2-<list_3>,3-<list_4>],[consistency(domain)]) list_2 = {0} list_3 = {2} list_4 = {0} Constraint exited.
Then we backtrack on list_1
yet another time, but no more
solutions are found:
Labeling [9, <list_1>]: indomain_up: <list_1> = 3 [...] <list_2>+2*<list_3>+3*<list_4>#=3+<list_2>+<list_3>+<list_4> list_2 = {0} list_3 = {1} list_4 = {0} Constraint failed. Labeling [9, <list_1>]: failed.