Square Puzzle Problem Solution with Constraint Programming

The issue is in your line_constraint/4 predicate. In it, you are posting some clpfd constraints inside a findall/3. This means that those constraints are only valid inside the findall/3. Here is a way to rewrite your predicate that keeps the constraints posted (given that you are using SICStus, I use the do loop style, which is just syntactic sugar around a recursive predicate):

line_constraints(Index, NumFilledCells, Starts, SquareSizes) :-
    (
      foreach(Start,Starts),
      foreach(SquareSize,SquareSizes),
      foreach(Usage,Usages),
      param(Index)
    do
      Intersect #<=> ( Start #=< Index #/\ Index #< Start + SquareSize),
      Usage #= Intersect * SquareSize
    ),
    sum(Usages, #=, NumFilledCells).

(Note that I changed the second inequality to be a strict one: The end of the square is right before Start + SquareSize.)

As you will probably experience, this formulation is pretty weak in terms of reducing the search space. One way to improve it (but I haven't tried it myself) would be to replace the lines_constraints/4 by some cumulative constraints.