Nous présentons un algorithme qui permet de résoudre efficacement les problèmes de complétion de quasi-groupes. Il se greffe sur un algorithme de Forward- Checking. Il élargit progressivement le nombre de valeurs à explorer. Pour un nombre donné de valeurs à explorer, et pour chaque variable, il choisit aléatoirement entre le nombre de valeurs à explorer et ce nombre moins un. La probabilité de choisir le nombre de valeurs à explorer est elle aussi augmentée progressivement. Sur 9900 problèmes de complétion de quasi-groupes d'ordre 20 et pour une bonne heuristique d'ordonnancement des valeurs utilisant une modélisation duale, notre algorithme donne de meilleurs résultats que le Forward-Checking, que les recommencements rapides aléatoires (Rapid Randomized Restarts), que l'élargissement itératif (Iterative Broadening) et que la recherche avec déviations limitées (Limited Discrepancy Search).