Problème de la couverture exacte
vignette|Pavage avec des pentominos d'un échiquier dans lequel on a retiré le carré 2x2 central.En informatique théorique, le problème de la couverture exacte (le problème exact cover en anglais) consiste à couvrir un ensemble de éléments, chaque éléments étant couverts par exactement un sous-ensemble. Ce problème est général et permet 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 résoudre un Sudoku ou le problème des huit reines. C'est un problème d'optimisation combinatoire NP-complet qui fait partie des 21 problèmes NP-complets de Karp. 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. Étant donné un ensemble U et une collection de sous-ensembles de U, une couverture exacte de U est une sous-collection de tel que tout élément de U est élément d'exactement un des ensembles de . En d'autres termes, une couverture exacte de U est une sous-collection de qui est une partition de U : les ensembles éléments de sont disjoints deux à deux, et leur union est U. Le problème de la couverture exacte est le problème de décider s'il existe ou non une couverture exacte pour un ensemble U et une collection de sous-ensembles de U. Ce problème est NP-complet ; et ce même si chaque sous-ensemble dans contient exactement 3 éléments ; cette restriction du problème est connu sous le nom de couverture exacte par 3-ensembles, et est souvent abrégé en X3C. Le problème de la couverture exacte est un exemple de problème de satisfaction de contraintes. Soit U = {0, 1, 2, 3, 4} et soit = {E, I, P} la collection de trois ensembles suivants : E = {0, 2, 4} ; I = {1, 3} ; P = {2, 3}. Alors, la sous-collection = {E, I} est une couverture exacte. En revanche, {E, P} n'est pas une couverture exacte : une raison suffisante est que 1 n'est contenu ni dans E ni dans P, une autre raison suffisante est que 2 est contenu à la fois dans E et P.
