Re: Constraint solver generates invalid solutions

Hi Markus,

sorry for the bug ... and for the late reply !
The bug is fixed in 1.4.2 which will be released in few days.

Here is a snapshot:
http://gprolog.univ-paris1.fr/unstable/gprolog-20121122.tgz

BTW: I attach a simple prolog file which performs the same test as yours 
but in a single file and then much faster.
I could test with N=14 (needs more than 1 day on my machine).

Daniel


Le 28/10/2012 13:26, Markus Triska a écrit :
> Hi Daniel,
>
> Daniel Diaz <[email protected]> writes:
>
>>    DATE++;
>>    if (DATE < 0)
>>       DATE = 1;
> I noticed you included this change in GNU Prolog 1.4.1. I have now
> constructed a simpler test case which shows that this does not fix the
> problem. GNU Prolog 1.4.1 still emits wrong answers within 5 days on an
> iMac (2.66 GHz) with the following test case, which uses only a single
> fd_all_different/1 constraint:
>
>     run :-
>             L = 20,
>             length(Ls, L),
>             fd_domain(Ls, 1, L),
>             fd_all_different(Ls),
>             fd_labeling(Ls),
>             portray_clause(Ls),
>             false.
>
> I'm attaching two files that let you reproduce the problem:
>
>     alldif.pl: Posts fd_all_different/1, labels and emits all solutions
>
>     alldif_verify.pl: Reads solutions from stdin and verifies them
>
> Just compile them as usual with "gplc alldif.pl" and "gplc
> alldif_verify", and then use them together with:
>
>     $ ./alldif | ./alldif_verify
>
> alldif_verify emits a line every 10.000th solution. The first few
> million solutions are all valid:
>
>     0.
>     1.
>     2.
>     3.
>     ....
>
> but after about 5 days, GNU Prolog 1.4.1 emits an answer that does not
> satisfy the fd_all_different/1 constraint:
>
>     ...
>     124964.
>     124965.
>     false - [1, 2, 3, 4, 5, 6, 7, 10, 16, 12, 14, 8, 18, 11, 20, 17, 19, 13, 9, 13].
>
> Please let me know if you need any further information.
>
> Thank you and all the best,
> Markus
>
>


-- 
Ce message a ete verifie par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a ete trouve.

_______________________________________________
Bug-prolog mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/bug-prolog

 /*
  * compile with: gplc alldiff.pl
  * run with: alldiff [N]
  * default to N = 10
  */

:- initialization(run).

run :-
	argument_list([AL]),
	catch(number_atom(L, AL), _, fail),
	run(L), !.

run :-
	run(10).


run(L) :-
	format('computing sols for ~d~n', [L]),
	g_assign(count_mod, 0),
	g_assign(count, 0),
        length(Ls, L),
        fd_domain(Ls, 1, L),
        fd_all_different(Ls),
        fd_labeling(Ls),
	check(Ls, L),
        fail.

run(L) :-
	g_read(count_mod, M),
	g_read(count, N),
	format('sols for ~d = #mod: ~d   count: ~d~n', [L, M, N]),
	factorial(L, M1, N1),
	(   M1 = M, N1 = N ->
	    write('OK !\n')
	;
	    format('ERROR !!! should be #mod: ~d   count: ~d~n', [M1, N1])
	),
	fail.

%run(_).

run(_) :-
	stop.

factorial( 0,              0,     1).
factorial( 1,              0,     1).
factorial( 2,              0,     2).
factorial( 3,              0,     6).
factorial( 4,              0,    24).
factorial( 5,              0,   120).
factorial( 6,              0,   720).
factorial( 7,              0,  5040).
factorial( 8,              0, 40320).
factorial( 9,              3, 62880).
factorial(10,             36, 28800).
factorial(11,            399, 16800).
factorial(12,           4790, 01600).
factorial(13,          62270, 20800).
factorial(14,         871782, 91200).
factorial(15,       13076743, 68000).
factorial(16,      209227898, 88000).
factorial(17,     3556874280, 96000).
factorial(18,    64023737057, 28000).
factorial(19,  1216451004088, 32000).
factorial(20, 24329020081766, 40000).


check(Ls, L) :-
	g_inc(count, N),
        (   N =:= 100000 ->	% if you modify this constant, modify the above table accordingly
            g_assign(count, 0),
	    g_inc(count_mod, M),
	    write(M), nl
	;
	    true
        ),
	g_assign(mask, 0),
	(   check1(Ls, L) ->
	    true
	;
	    portray_clause(false-Ls), halt
        ).


check1([], _).

check1([X|Ls], L) :-
	integer(X),
	X >= 1,
	X =< L,
	g_test_reset_bit(mask, X),
	g_set_bit(mask, X),
	check1(Ls, L).