FDBG An Example Session (SICStus Prolog)

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:

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.

| ?- 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)).
[…]

| ?- [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

| ?- 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

| ?- 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

<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.

10.14.3.6 An Example Session