  Search strategies are crucial to efficiently solve constraint satisfaction
problems. However, programming search strategies in the existing constraint
solvers is a daunting task and constraint-based languages usually have
compositionality issues. We propose spacetime programming, a paradigm extending
the synchronous language Esterel and timed concurrent constraint programming
with backtracking, for creating and composing search strategies. In this
formalism, the search strategies are composed in the same way as we compose
concurrent processes. Our contributions include the design and behavioral
semantics of spacetime programming, and the proofs that spacetime programs are
deterministic, reactive and extensive functions. Moreover, spacetime
programming provides a bridge between the theoretical foundations of
constraint-based concurrency and the practical aspects of constraint solving.
We developed a prototype of the compiler that produces search strategies with a
small overhead compared to the hard-coded ones.
