Le formalisme des problèmes de satisfaction de contraintes (CSP) et les méthodes associées offrent un cadre théorique de plus en plus utilisé pour traiter les problèmes d'Intelligence Artificielle. Toutefois, la plupart des méthodes se concentrent sur le calcul d'une solution ce qui constitue un objectif trop limité. Nous introduisons dans cette thèse la notion de relation complète qui permet de calculer et de représenter de façon compacte des ensembles de solutions. Nous proposons d'abord une méthode qui génère une partition des solutions d'un CSP binaire par relations complètes Cette méthode met en œuvre une décomposition structurelle et une décomposition des contraintes par identification de symétries (calcul d'interchangeabilité). Sa complexité, qui est fonction de la taille d'un transversal minimal du graphe, n'est pas liée au nombre de solutions, à l'inverse des méthodes énumératives. Une évaluation expérimentale sur des problèmes jouets en démontrent le bon comportement. Nous montrons ensuite que cette méthode relève d'un schéma plus général qui consiste a résoudre le CSP dual d'un CSP pour obtenir une partition de ses solutions. Il est possible de construire un dual binaire pour tout CSP binaire : certaines classes polynomiales s'avèrent alors êtres stables par passage au dual binaire, assurant ainsi un coût polynomial pour le calcul d'un sous-ensemble des solutions. Nous proposons enfin une extension de l'algorithme backtrack standard pour le calcul de quelques solutions. Expérimentée sur problèmes aléatoires, cette extension entraîne un surcoût modeste par rapport au calcul d'une seule solution bien qu'elle fournisse en meilleur cas un nombre exponentiel de solutions.