I made two implementations to solve Shikaku puzzles. One uses Top,Left,Width and Height (TLWH) as parameters for each rectangle, the other Top,Left,Bottom,Right (TLBR).
For some reason the one using TLBR is much faster, but I'm not really sure why. So I was wondering if there is a way to see what constraint is taking so much longer in the TLWH implementation.
Is there a way to profile ECLiPSe CLP solutions?
I'm currently using TkEclipse on Windows.
It is quite typical of CLP programs that there is no simple relationship between the code (in particular the part that models the problem) and its execution performance. The most blatant example of this is that is it often possible to drastically reduce runtimes via adding redundant constraints.
The main factor in CLP performance is the size and shape of the search tree, which, fortunately and unfortunately, depends on many factors. Fortunately, because it gives us many options for influencing the search tree. Unfortunately, because it makes predicting performance hard.
The second factor is the strength of constraint propagation, which is somewhat more directly linked to the way the model has been formulated. For example, a single "global" constraint (which works on many variables at once) typically provides stronger propagation than an equivalent formulation with many smaller constraints. Propagation strength in turn influences search tree size.
So, to find out why your two implementations behave so differently, the first step is to compare their search trees. The simplest way to do that is to look at the number of backtracks required to find a solution. If you use the search/6 library predicate, you can get a count via the Options argument:
search(Xs, ..., ..., ..., ..., [backtrack(BT)]),
printf("Solution found after %d backtracks%n", [BT]),
I used this Sikaku code as my TLBR model, and a modified version as TLWH model. For finding the solution for the p(15,1) problem, these need
TLBR: 0 backtracks
TLWH: 171 backtracks
Obviously, the two programs do very different things. In particular, the TLBR model seems much "tighter" and doesn't require much search!
To find out why, I compared the state of computation just before the search phase is started (I just removed the call to the search routine, and printed the grid with its partial results - you can also use the tracer and the term inspector tool, or other visualization tools). It turns out that in the TLBR model, many rectangles already have their final placement (i.e. their coordinate variables are already instantiated), while in the TLWH model none of them have (their variables still can take many values).
A closer look at a subproblem suggests the reason. Consider only the horizontal coordinates, and suppose L is the left edge, R the right edge, and W the width of the rectangle. L and W's domains are given, and the rectangle must cover the point 9. In the TLBR model, this leads to the constraints:
?- L::6..9, W::1..4, R#=L+W-1, L#=<9, 9#=<R.
L = L{6..9}
W = W{1..4}
R = R{9..12}
There is 1 delayed goal.
Yes (0.00s cpu)
while in the TLWH model, we have to write the last constraint differently, because we don't have an R variable available at this point:
?- L::6..9, W::1..4, Rimplicit#=L+W-1, L#=<9, 9#=<L+W-1.
L = L{6..9}
W = W{1..4}
Rimplicit = Rimplicit{6..12}
There are 2 delayed goals.
Yes (0.00s cpu)
We see in the TLWH model that the domain of the right edge, when computed from L+W-1, does not reflect the information that it must be at least 9. We have lost some propagation strength by not factoring out the L+W-1 subexpression, which, I think, this is the main reason for the weaker propagation.
There is another reason for the difference in the search trees, which is that we simply have different variables to label: [L,R] in one case, [L,W] in the other. In particular when using a domain-sensitive variable selection heuristic, this can cause very different behaviour.