Dans le cadre de la résolution des problèmes de satisfaction de contraintes, nous présentons une nouvelle méthode complète basée sur des améliorations de " Limited Discrepancy Search " [Harvey & Ginsberg 1995]. Cette méthode, intitulée " Minimal Discrepancy Search " ( DS), peut être considérée comme la fusion de deux nouvelles variantes de LDS ; celles-ci mettent en oeuvre des techniques d'apprentissage au cours de la recherche : - " Permuted Limited Discrepancy Search " qui exploite les échecs rencontrés lors de l'exploration de l'arbre de recherche et en déduit un ordre sur les variables. Cet ordre minimise le nombre de divergences et accélère la résolution dans le cas d'un problème soluble. - " Restricted Discrepancy Search ", méthode permettant de déterminer, sans pour autant réaliser toutes les itérations de LDS, si le problème est sur-contraint. Dans ce cas, on abandonne la recherche prématurément (et avantageusement). Les performances de ces méthodes sont évaluées suivant le temps nécessaire pour aboutir à une solution, ou à la preuve de l'absence d'une solution, et le nombre de noeuds générés dans l'arbre de recherche correspondant. Pour attester de l'efficacité de DS, des comparaisons avec d'autres méthodes ont été menées, suivant la taille et le taux de contraintes des problèmes testés. " Forward Checking " est ainsi utilisé pour des problèmes de taille réduite et relativement peu contraints ; pour des problèmes de grande taille et plus fortement contraints, nous utilisons " mac3cache ", proposé par [Zhang et al. 2004]. Dans tous les cas, DS s'avère très performante et surclasse les autres méthodes.