Problème de la couverture exacte
De Wikipedia, l'encyclopédie encyclopedia
En informatique théorique, le problème de la couverture exacte (exact cover en anglais) consiste à couvrir un ensemble d'éléments, chaque éléments étant couverts par exactement un sous-ensemble. Ce problème est général et permet, par exemple, de calculer une couverture (ou pavage) d'un ensemble de cellules par des pentominos : chaque cellule doit être couverte par un et un seul pentominos. Il permet aussi de résoudre un Sudoku ou le problème des huit reines. C'est un problème d'optimisation combinatoire NP-complet[1] qui fait partie des 21 problèmes NP-complets de Karp[2].
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
L'algorithme X de Donald Knuth trouve toutes les solutions au problème de couverture exacte. Cet algorithme est nommé DLX quand il est implémenté en utilisant la structure de données des dancing links[3].