Optimizing pathfinding in Constraint Logic Programming with Prolog

I am working on a small prolog application to solve the Skyscrapers and Fences puzzle.

An unsolved puzzle:

A solved puzzle:

When I pass the program already solved puzzles it is quick, almost instantaneous, to validate it for me. When I pass the program really small puzzles (2x2, for example, with modified rules, of course), it is also quite fast to find a solution.

The problem is on computing puzzles with the "native" size of 6x6. I've left it running for 5 or so hours before aborting it. Way too much time.

I've found that the part that takes the longest is the "fences" one, not the "skyscrapers". Running "skyscrapers" separately results in a fast solution.

Here's my algorithm for fences:

• Vertices are represented by numbers, 0 means the path doesn't pass through that particular vertex, > 1 represents that vertex's order in the path.
• Constrain each cell to have the appropriate amount of lines surrounding it.
  • That means that two vertexes are connected if they have sequential numbers, e.g., 1 -> 2, 2 -> 1, 1 -> Max, Max -> 1 (Max is the number for the last vertex in the path. computed via maximum/2)
• Make sure each non-zero vertex has at least two neighboring vertices with sequential numbers
• Constrain Max to be equal to (BoardWidth + 1)^2 - NumberOfZeros (BoardWidth+1 is the number of vertices along the edge and NumberOfZeros is computed via count/4).
• Use nvalue(Vertices, Max + 1) to make sure the number of distinct values in Verti