Algorithme X de Knuth

L'algorithme X de Donald Knuth est un algorithme récursif (en), de parcours en profondeur et à retour sur trace. Il permet de trouver des solutions au problème de la couverture exacte, représenté sous la forme d'une matrice contenant des 0 et des 1. L'objectif est de déterminer un sous-ensemble de lignes tel que le chiffre 1 n'apparaisse dans chaque colonne qu'une et une seule fois.