Up to date, most of the research on constraint satisfaction has considered crisp constraints. Currently new types of constraints are being considered, allowing for intermediate satisfaction degrees between complete satisfaction and complete violation. Modeling these new constraint types in a fuzzy environment, generates a new kind of problem denominated fuzzy constraint satisfaction. We present an algorithmic approach to solve this problem, using the branch-and-bound algorithm and reusing existing techniques developed in the contest of crisp constraints. Empirical results show the feasibility of our approach and confirm the applicability of previously used techniques to the fuzzy case.