CuFrog solving using CLPFD

3
votes

Ok, so I have this puzzle that is called the CuFrog, that consists in filling a 3x3x3 cube with a number in each position but leaping over a position when going from one to the other. For instance, considering a flattened cube, the valid position to the right of (1,1) on side 1 would be (3,1) on side 1.

So I'm using Constraints in Prolog to do this and I've given the domain of each variable (1 to 54), I've said they must all be different and that, for each position, one of the positions in the set right-left-down-up has to be the current value of such position + 1.

Also, I've given an entry point to the puzzle, which means I placed the number 1 already on the first position.

Thing is, SICStus is not finding me an answer when I'm labelling the variables. :( It seems I must be missing a restriction somewhere or maybe I'm doing something wrong. Can anyone help?

Thanks.

1
prologpuzzleclpfd
Use asserta(clpfd:full_answer)). And then enter the query without labeling! You have definitely not missed a restriction, it is rather the opposite: You are restricting too much! – false
I'm sorry, but how should I use that in my code? Like this? length(Vars,54), domain(Vars,1,54), restriction_predicate(), asserta(clpfd:full_answer). %labelling([min],Vars) -- This is what I was doing. – Sidner
Ah, ok. Next to the use_module line, then. – Sidner
You only need to enter it once at the | ?- prompt – false
But isn't it the labelling that instantiates the variables in Vars according to the restrictions? Cause doing it like this I get no definite answer, only domains... – Sidner

1 Answers

2
votes

So you say the CLP(FD) doesn't find a solution. Do you mean it terminates with "no" or do you mean it doesn't terminate?

The problem looks like a Hamiltonian path problem. It could be that the search needs exponential time, and simply doesn't terminate in practical time.

In this particular case, giving restrictions like symmetry breaking heuristics, could in fact reduce the search time! For example from your starting point, you could fix the search in 2 directions, the other directions can be derived later.

So if the answer is "No", this means too many restrictions. If the answer is that it doesn't terminate, this means not enough restrictions or impossible to practically solve.

Despite all the brute force you put into searching a path, it might later turn out that a solution is systematic. Or you might get the idea by yourself.

Bye