CLP over Finite Set

Help! PlDoc
1

I’m analyzing games. Imagine applying Sudoku-like constraints to a board of (finitely many) arbitrary non-integer terms (house(green), soldier, cow, etc). For example, a soldier cannot be beside a house, there is one cow per column, etc.
The optimizations in clpfd do not (seem to) exist for Finite Sets (of arbitrary ground terms).
Doing something naive like this is not performant when generating solutions:

distinct([]).
distinct([H|T]) :- maplist(dif(H),T), distinct(T).

values_domain([], _).
values_domain([H|T], Domain) :- member(H, Domain), values_domain(T, Domain).

Am I missing something obvious? Is the common practice to map one’s set to integers, solve, then map back?

Thanks.

1 Like
2

This is known as an Einstein puzzle or Zebra puzzle (Wikipedia).

For a non-constraint example see

https://swish.swi-prolog.org/example/houses_puzzle.pl

For a constraint example see

then scroll down to Zebra Puzzle

1 Like
3

Thanks. So it seems the answer to my question

Is the common practice to map one’s set to integers, solve, then map back?

is YES.

Zebra Puzzle
…
Such puzzles can be very conveniently solved by first translating the entities to integers , and then using your Prolog system’s declarative integer arithmetic to state the given hints as relations between variables whose domains are sets of integers.
- Logic Puzzles with Prolog

4

If you’re using clpfd that’s correct; clpfd is an instance of CLP over the finite domain of integers. There are other CLP’s for other domains, e.g., clpb (booleans), clpq (rationals), etc.

1 Like