Node:FDBG An Example Session, Previous:FDBG Annotation, Up:FDBG Basics

An Example Session

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.