bug-prolog
[Top][All Lists]

## Constraint solver generates invalid solutions

 From: Markus Triska Subject: Constraint solver generates invalid solutions Date: Fri, 18 Feb 2011 19:38:01 +0100

```On a 2009 iMac (2.66 Intel Core 2 Duo, 4 GB RAM) with OSX 10.5.8,
gprolog 1.3.1 produces invalid solutions (that is, they do not satisfy
all posted constraints) to a finite domain constraint problem, as you
can verify with the attached programs.

The first program, fd_decompose.pl, solves a certain combinatorial
problem (it enumerates all supersimple 16-4-2 designs that are
decomposable, that is, each of them is the union of two 16-4-1 designs;
"supersimple" means that every two blocks share at most two points). The
second program, fd_decompose_verify.pl, is almost identical to the first
program, except that it does not generate solutions, but reads them from
standard input and uses the exact same constraint formulation to check
whether the solution (is ground and) satisfies all constraints; a simple

Compile both programs as usual with "gplc fd_decompose.pl" and "gplc
fd_decompose_verify.pl", and then use them together with:

\$ ./fd_decompose | ./fd_decompose_verify

The first few generated solutions are all valid:

0 1 2 3 4  ...

but, after about 2 weeks of computation time, I get an invalid one:

... 22218 22219 wrong - ([[0, 1, 5, 14], [0, 2, 8, 13], [0, 3, 7,
11], [0, 4, 9, 12], [0, 6, 10, 15], [1, 2, 4, 6], [1, 3, 8, 9], [1,
7, 10, 12], [1, 11, 13, 15], [2, 3, 5, 12], [2, 7, 9, 15], [2, 10,
11, 14], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3,
4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6]] - [[0, 1, 7, 9],
[0, 2, 12, 14], [0, 3, 5, 15], [0, 4, 6, 8], [0, 10, 11, 13], [1, 2,
10, 15], [1, 3, 4, 13], [1, 5, 8, 12], [1, 6, 11, 14], [2, 3, 7, 8],
[2, 4, 9, 11], [2, 5, 6, 13], [3, 6, 10, 12], [3, 5, 7, 10], [3, 5,
7, 10], [3, 5, 7, 10], [3, 5, 7, 10], [3, 5, 7, 10], [3, 5, 7, 10],
[3, 5, 7, 14]]).

Please let me know if you need any further information.

Thank you and all the best,
Markus

```

fd_decompose.pl
Description: Binary data

fd_decompose_verify.pl
Description: Binary data