Stream: Elpi users & devs

Topic: all_different constraint

Théo Laurent (Jul 21 2022 at 09:17):

Enrico Tassi said:

I did not try to run it (you need to adapt the syntax a little), but this seems a way to do it: https://gist.github.com/luan/1995582

This GNU Prolog version use fd_all_different which add constraints to the resolution. How to do that with elpi (efficiently)?

Enrico Tassi (Jul 21 2022 at 13:00):

This is not super efficient, but does what you want:

pred alldiff i:list int.
alldiff L :- not (distinct L), !, fail.
alldiff L :- std.filter L var VL, if (VL = []) true (declare_constraint (alldiff L) VL).

pred distinct i:list int.
distinct [].
distinct [X|XS] :- var X, !, distinct XS.
distinct [X|XS] :- not(present X XS), distinct XS.

pred present i:int, i:list int.
present N [X|XS] :- var X, !, present N XS.
present N [N|_] :- !.
present N [_|XS] :- present N XS.

main :-
  alldiff [A,B,C],
  A = 1,
  not(B = 1),
  B = 2,
  not(C = 1),
  not(C = 2),
  C = 3.

Enrico Tassi (Jul 21 2022 at 13:07):

You can refine it a little, by storing in alldiff an int.set with the concrete values, but you would still need to scan (and filter) the list to find out which variable was assigned. There is no language feature which tell you which variable is causing the resumption of a constraint.

Théo Laurent (Jul 27 2022 at 19:34):

Update: I still did not manage to get a practical sudoku solver in elpi, if anyone has tried it, I'm will be more than happy to look at the solution :)

Enrico Tassi (Aug 03 2022 at 08:31):

Do you mean that it is too slow?

Last updated: Oct 13 2024 at 01:02 UTC