Bounded-error estimation is the estimation of the parameter or state vector of a model from experimental data, under the assumption that some suitably defined errors should belong to some prior feasible sets. When the model outputs are linear in the vector to be estimated, a number of methods are available to contain all estimates that are consistent with the data within simple sets such as ellipsoids, orthotopes or parallelotopes, thereby providing guaranteed set estimates. In the non-linear case, the situation is much less developed and there are very few methods that produce such guaranteed estimates. In this paper, the problem of characterizing the set of all state vectors that are consistent with all data in the case of non-linear discrete-time systems is cast into the more general framework of constraint satisfaction problems. The state vector at time k should be estimated either on-line from past measurement only or off-line from a series of measurements that may include measurements posterior to k. Even in the causal case, prior information on the future value of the state and output vectors, due for instance to physical constraints, is readily taken into account. Algorithms taken from the literature of interval constraint propagation are extended by replacing intervals by more general subsets of real vector spaces. This makes it possible to propose a new algorithm that contracts the feasible domain for each uncertain variable optimally (i.e. no smaller domain could be obtained) and efficiently.