Performance characteristics of core.logic with many finite domain constraints

I'm learning relational programming in miniKanren and I decided to implement a time scheduling system. Basically, it boils down to three relations over finite domain.

First, there is a time strip that has a start, duration, end and occurs in a space:

(l/defne stripo
  "Defines time strip relationship. Time strip start must be before end, and have a duration."
  [work] ([[start duration end _]]
          (fd/+ start duration end)))

Then, there is a happens-before relation on a list of strips (which is a list of 4-element lists). This is a pairwise relationship between end and start of two events:

(l/defne happens-beforo
         "Defines a happens-before relationship between consecutive time strips in a list."
         [elements]
         ([[]])
         ([[a]])
         ([[a b . d]]
          (l/matche [a b] ([ [_ _ e _] [s _ _ _] ] (fd/<= e s)))
          (happens-beforo (l/llist b d))))

Lastly, there is a non-overlap relationship that states that two time strips cannot overlap when they share the same space:

(l/defne non-overlappo
  "Two time strips must not overlap in time, if they share the same space"
  [a b]
  ([[_ _ _ sp1] [_ _ _ sp2]]
   (l/conde
     [(l/== sp1 sp2)
      (l/conde
        [(happens-beforo [a b])]
        [(happens-beforo [b a])])]
     [(l/!= sp1 sp2)])))

I can run very long queries for chains of happens-beforo relationships, thousands of time strips are fine. The problem starts arising when I constrain the space of those time strips. This is a function that does it:

(l/defne constrain-spaceo
  "This constraint will assure that all time strips within the argument
  obey non-overlapping relationship with each other. Quadratic."
  [strips]
  ([[]])
  ([[w . ws]]
   (let [space' (l/defne space' [c a]
                  ([_ []])
                  ([_ [f . d]]
                   (non-overlappo c f)
                   (space' c d)))]
     (l/all (space' w ws) (constrain-spaceo ws)))))

For a list of strips q, it establishes a non-overlappo relationship between each two elements. Since it is a bi-directional relation, it is less than n^2.

When I use constrain-spaco for as little as 10 strips, the search time blows up and I am not able to produce any results.

So far I've been experimenting with ways to reduce this time, and it seems that it is related to the amount of strips competing for one space, regardless of how many strips there are in total. If I create two sets of strips, one in space 0 and the other in space 1 and apply constrain-spaco on the whole list of strips, then the time is the sum of the times of calculation of these strips separately.

My question are:

1. why does the amount of finite domain constraints impact the time so much? I was under the impression that the amount of constraints helps with search time.
2. Is there any way to lower the search time? Perhaps change the data representation?

I'm not certain of this, but I would guess that it is actually because of the condes in non-overlappo.

constrain-spaco on 10 strips means 10+9+...+1 = 55 calls of non-overlappo, and each non-overlappo has 2 possible ways to go (from the inner conde), giving us (at a worst-case without compiler optimization) 2^55 options.

Maybe if you use a cut, like conda, the performance will get better.