Cobertura exacta

En el campo matemático de la combinatoria , dada una colección de subconjuntos de un conjunto , una cobertura exacta es una subcolección de tal que cada elemento en está contenido en exactamente un subconjunto en . Se dice que cada elemento en está cubierto por exactamente un subconjunto en . ^[1] Una cobertura exacta es un tipo de cobertura . Es polinomial no determinista en tiempo (NP) completa y tiene una variedad de aplicaciones, que van desde la optimización de los horarios de vuelos de las aerolíneas, la computación en la nube y el diseño de circuitos electrónicos . ^[2]${\displaystyle {\mathcal {S}}}$ ${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$${\estilo de visualización X}$ ${\displaystyle {\mathcal {S}}^{*}}$

En otras palabras, es una partición de que consta de subconjuntos contenidos en . ${\displaystyle {\mathcal {S}}^{*}}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}}$

El problema de cobertura exacta para encontrar una cobertura exacta es un tipo de problema de satisfacción de restricciones . Los elementos de representan elecciones y los elementos de representan restricciones. ${\displaystyle {\mathcal {S}}}$${\estilo de visualización X}$

Un problema de cobertura exacta implica la relación de contenido entre subconjuntos y elementos. Pero un problema de cobertura exacta puede representarse mediante cualquier relación heterogénea entre un conjunto de opciones y un conjunto de restricciones. Por ejemplo, un problema de cobertura exacta es equivalente a un problema de conjunto de impacto exacto , una matriz de incidencia o un grafo bipartito .

En informática , el problema de cobertura exacta es un problema de decisión para determinar si existe una cobertura exacta. El problema de cobertura exacta es NP-completo ^[3] y es uno de los 21 problemas NP-completos de Karp . ^[4] Es NP-completo incluso cuando cada subconjunto en S contiene exactamente tres elementos; este problema restringido se conoce como cobertura exacta por 3-conjuntos , a menudo abreviado X3C. ^[3]

El algoritmo X de Knuth es un algoritmo que encuentra todas las soluciones a un problema de cobertura exacta. DLX es el nombre que se le da al algoritmo X cuando se implementa de manera eficiente utilizando la técnica Dancing Links de Donald Knuth en una computadora. ^[5]

El problema de cobertura exacta se puede generalizar ligeramente para involucrar no solo restricciones de exactamente una vez sino también restricciones de como máximo una vez .

Encontrar teselas de pentominó y resolver sudokus son ejemplos notables de problemas de cobertura exacta. El problema de las n reinas es un problema de cobertura exacta generalizado.

Dada una colección de subconjuntos de un conjunto , una cobertura exacta de es una subcolección de que satisface dos condiciones: ${\displaystyle {\mathcal {S}}}$${\estilo de visualización X}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$

• La intersección de dos subconjuntos distintos cualesquiera en está vacía , es decir, los subconjuntos en son disjuntos por pares . En otras palabras, cada elemento en está contenido en, como máximo, un subconjunto en .${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}^{*}}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$
• La unión de los subconjuntos en es , es decir, los subconjuntos en cubren . En otras palabras, cada elemento en está contenido en al menos un subconjunto en .${\displaystyle {\mathcal {S}}^{*}}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$ ${\estilo de visualización X}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$

En resumen, una cobertura exacta es exacta en el sentido de que cada elemento en está contenido en exactamente un subconjunto en . ${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$

De manera equivalente, una cubierta exacta de es una subcolección de esa partición . ${\estilo de visualización X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$ ${\estilo de visualización X}$

Para que exista una cobertura exacta de es necesario que: ${\estilo de visualización X}$

• La unión de los subconjuntos en es . En otras palabras, cada elemento en está contenido en al menos un subconjunto en .${\displaystyle {\mathcal {S}}}$${\estilo de visualización X}$${\estilo de visualización X}$${\displaystyle {\mathcal {S}}}$

Si el conjunto vacío está contenido en , entonces no importa si está o no en una cobertura exacta. Por lo tanto, es típico suponer que: ${\displaystyle \conjunto vacío}$${\displaystyle {\mathcal {S}}}$

• El conjunto vacío no está en . En otras palabras, cada subconjunto en contiene al menos un elemento.${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}^{*}}$

Sea una colección de subconjuntos de un conjunto tales que: ${\displaystyle {\mathcal {S}}=\{N,O,P,E\}}$${\displaystyle X=\{1,2,3,4\}}$

• ${\displaystyle N=\{\}}$,
• ${\displaystyle O=\{1,3\}}$,
• ${\displaystyle P=\{1,2,3\}}$, y
• ${\displaystyle E=\{2,4\}}$.

La subcolección es una cobertura exacta de , ya que los subconjuntos y son disjuntos y su unión es . ${\estilo de visualización \{O,E\}}$${\estilo de visualización X}$${\displaystyle O=\{1,3\}}$${\displaystyle E=\{2,4\}}$${\displaystyle X=\{1,2,3,4\}}$

La subcolección también es una cobertura exacta de . Incluir el conjunto vacío no supone ninguna diferencia, ya que es disjunto con todos los subconjuntos y no cambia la unión. ${\displaystyle \{N,O,E\}}$${\estilo de visualización X}$${\displaystyle N=\{\}}$

La subcolección no es una cobertura exacta de . Aunque la unión de los subconjuntos y es , la intersección de los subconjuntos y , , no está vacía. Por lo tanto, los subconjuntos y no cumplen el requisito de disyunción de una cobertura exacta. ${\estilo de visualización \{E,P\}}$${\estilo de visualización X}$${\estilo de visualización E}$${\estilo de visualización P}$${\displaystyle \{1,2,3,4\}=X}$${\estilo de visualización E}$${\estilo de visualización P}$${\estilo de visualización \{2\}}$${\estilo de visualización E}$${\estilo de visualización P}$

La subcolección tampoco es una cobertura exacta de . Aunque y son disjuntos, su unión no es , por lo que no cumplen el requisito de cobertura . ${\estilo de visualización \{N,P\}}$${\estilo de visualización X}$${\estilo de visualización N}$${\estilo de visualización P}$${\estilo de visualización X}$

Por otra parte, no existe una cobertura exacta —de hecho, ni siquiera una cobertura— de porque es un subconjunto propio de : Ninguno de los subconjuntos de contiene el elemento 5. ${\displaystyle Y=\{1,2,3,4,5\}}$${\displaystyle \bigcup {\mathcal {S}}=\{1,2,3,4\}}$${\estilo de visualización Y}$${\displaystyle {\mathcal {S}}}$

Sea S = { A , B , C , D , E , F } una colección de subconjuntos de un conjunto X = {1, 2, 3, 4, 5, 6, 7} tales que:

• A = {1, 4, 7};
• B = { 1 , 4 };
• C = {4, 5, 7};
• D = { 3 , 5 , 6 };
• E = {2, 3, 6, 7}; y
• F = { 2 , 7 }.

La subcolección S ^* = { B , D , F } es una cobertura exacta, ya que cada elemento está cubierto por (contenido en) exactamente un subconjunto seleccionado, como lo deja claro el resaltado.

Además, { B , D , F } es la única cobertura exacta, como demuestra el siguiente argumento: Debido a que A y B son los únicos subconjuntos que contienen el elemento 1, una cobertura exacta debe contener A o B , pero no ambos. Si una cobertura exacta contiene A , entonces no contiene B , C , E o F , ya que cada uno de estos subconjuntos tiene el elemento 1, 4 o 7 en común con A . Entonces D es el único subconjunto restante, pero la subcolección { A , D } no cubre el elemento 2. En conclusión, no hay una cobertura exacta que contenga A . Por otro lado, si una cobertura exacta contiene B , entonces no contiene A o C , ya que cada uno de estos subconjuntos tiene el elemento 1 o 4 en común con B . Debido a que D es el único subconjunto restante que contiene el elemento 5, D debe ser parte de la cobertura exacta. Si una cobertura exacta contiene D , entonces no contiene E , ya que E tiene los elementos 3 y 6 en común con D . Entonces F es el único subconjunto restante, y la subcolección { B , D , F } es de hecho una cobertura exacta. Vea el ejemplo en el artículo sobre el algoritmo X de Knuth para una versión basada en matrices de este argumento.

Un problema de cobertura exacta se define por la relación heterogénea que existe entre una colección S de subconjuntos y un conjunto X de elementos. Pero no hay nada fundamental acerca de los subconjuntos y los elementos.

Una representación de un problema de cobertura exacta surge siempre que existe una relación heterogénea R ⊆ S × X entre un conjunto S de opciones y un conjunto X de restricciones y el objetivo es seleccionar un subconjunto S ^* de S tal que cada elemento en X esté R ^T -relacionado con exactamente un elemento en S ^* . Aquí R ^T es el inverso de R .

En general, R ^T restringida a X × S ^* es una función de X a S ^* , que asigna cada elemento en X al único elemento en S ^* que está R -relacionado con ese elemento en X . Esta función es sobre , a menos que S ^* contenga un elemento (similar al conjunto vacío) que no esté R -relacionado con ningún elemento en X .

Las representaciones de un problema de cobertura exacta incluyen un problema de conjunto de impacto exacto, una matriz de incidencia y un gráfico bipartito.

En matemáticas , dado un conjunto S y una colección X de subconjuntos de S , un conjunto de coincidencia exacta S ^* es un subconjunto de S tal que cada subconjunto de X contiene exactamente un elemento de S ^* . Se dice que cada subconjunto de X es afectado por exactamente un elemento de S ^* .

El problema del conjunto de golpes exactos es una representación de un problema de cobertura exacto que implica la relación está contenido en en lugar de contiene .

Por ejemplo, sea S = { a , b , c , d , e , f } un conjunto y X = { I , II , III , IV , V , VI , VII } una colección de subconjuntos de S tales que:

• Yo = { a , b }
• II = { e , f }
• III = { d , e }
• IV = { a , b , c }
• V = { c , d }
• VI = { d , e }
• VII = { a , c , e , f }

Entonces S ^* = { b , d , f } es un conjunto de impacto exacto, ya que cada subconjunto en X es impactado por (contiene) exactamente un elemento en S ^* , como lo deja claro el resaltado.

Este ejemplo exacto de conjunto de golpes es esencialmente el mismo que el ejemplo detallado anteriormente. Mostrar la relación contenida en (∈) de elementos a subconjuntos deja en claro que simplemente hemos reemplazado los subconjuntos con letras por elementos y los elementos numerados por subconjuntos:

• a ∈ I , IV , VII ;
• b ∈ Yo , IV ;
• c ∈ IV , V , VII ;
• d ∈ III , V , VI ;
• e ∈ II , III , VI , VII ; y
• f ∈ II , VII .

La relación contiene puede representarse mediante una matriz de incidencia .

La matriz incluye una fila para cada subconjunto de S y una columna para cada elemento de X. La entrada en una fila y columna en particular es 1 si el subconjunto correspondiente contiene el elemento correspondiente, y es 0 en caso contrario.

En la representación matricial, una cobertura exacta es una selección de filas de modo que cada columna contenga un 1 en exactamente una fila seleccionada. Cada fila representa una opción y cada columna representa una restricción.

Por ejemplo, la relación contenida en el ejemplo detallado anterior se puede representar mediante una matriz de incidencia de 6×7:

Nuevamente, la subcolección S ^* = { B , D , F } es una cobertura exacta, ya que cada columna contiene un 1 en exactamente una fila seleccionada, como lo deja claro el resaltado.

Consulte el ejemplo en el artículo sobre el algoritmo X de Knuth para obtener una solución basada en matrices para el ejemplo detallado anterior.

A su vez, la matriz de incidencia también puede considerarse como la descripción de un hipergrafo . El hipergrafo incluye un nodo para cada elemento de X y una arista para cada subconjunto de S ; cada nodo está incluido en exactamente una de las aristas que forman la cubierta.

La relación contiene puede representarse mediante un gráfico bipartito .

Los vértices del gráfico se dividen en dos conjuntos disjuntos, uno que representa los subconjuntos en S y otro que representa los elementos en X. Si un subconjunto contiene un elemento, una arista conecta los vértices correspondientes en el gráfico.

En la representación gráfica, una cobertura exacta es una selección de vértices correspondientes a subconjuntos tales que cada vértice correspondiente a un elemento está conectado exactamente a un vértice seleccionado.

Por ejemplo, la relación contenida en el ejemplo detallado anterior se puede representar mediante un gráfico bipartito con 6+7 = 13 vértices:

Nuevamente, la subcolección S ^* = { B , D , F } es una cobertura exacta, ya que el vértice correspondiente a cada elemento en X está conectado exactamente a un vértice seleccionado, como lo deja claro el resaltado.

El algoritmo X es el nombre que Donald Knuth dio al "enfoque de prueba y error más obvio" para encontrar todas las soluciones al problema de cobertura exacta. ^[5] Técnicamente, el algoritmo X es un algoritmo recursivo , no determinista , de profundidad y de retroceso .

Cuando el algoritmo X se implementa de manera eficiente utilizando la técnica Dancing Links de Donald Knuth en una computadora, Knuth lo llama DLX. Utiliza la representación matricial del problema, implementada como una serie de listas doblemente enlazadas de los 1 de la matriz: cada elemento 1 tiene un enlace con el siguiente 1 arriba, abajo, a la izquierda y a la derecha de sí mismo. Debido a que los problemas de cobertura exacta tienden a ser dispersos, esta representación suele ser mucho más eficiente tanto en tamaño como en tiempo de procesamiento requerido. DLX luego utiliza la técnica Dancing Links para seleccionar rápidamente permutaciones de filas como posibles soluciones y para retroceder (deshacer) de manera eficiente las suposiciones erróneas. ^[5]

En un problema de cobertura exacta estándar, cada restricción debe cumplirse exactamente una vez. Es una generalización sencilla relajar un poco este requisito y permitir la posibilidad de que algunas restricciones primarias deban cumplirse con exactamente una opción, pero otras restricciones secundarias puedan cumplirse con una sola opción como máximo .

Como explica Knuth, un problema de cobertura exacta generalizado se puede convertir en un problema de cobertura exacta equivalente simplemente añadiendo una fila por cada columna secundaria, que contenga un solo 1 en esa columna. ^[6] Si en una solución candidata particular se satisface una columna secundaria particular, entonces no se necesita la fila agregada. Pero si la columna secundaria no se satisface, como se permite en el problema generalizado pero no en el problema estándar, entonces se puede seleccionar la fila agregada para garantizar que se satisfaga la columna.

Pero Knuth continúa explicando que es mejor trabajar directamente con el problema generalizado, porque el algoritmo generalizado es más simple y rápido: Un simple cambio en su algoritmo X permite manejar directamente las columnas secundarias.

El problema de las N reinas es un ejemplo de un problema de cobertura exacta generalizado, ya que las restricciones correspondientes a las diagonales del tablero de ajedrez tienen un recuento máximo de reinas en lugar de un recuento exacto.

Debido a su carácter NP-completo, cualquier problema en NP puede reducirse a problemas de cobertura exacta, que luego pueden resolverse con técnicas como Dancing Links. Sin embargo, para algunos problemas bien conocidos, la reducción es particularmente directa. Por ejemplo, el problema de colocar pentominós en un tablero y resolver un sudoku pueden considerarse ambos como problemas de cobertura exacta.

El problema de cubrir un tablero de 60 cuadrados con los 12 pentominós libres diferentes es un ejemplo de un problema de cobertura exacta, como explica Donald Knuth en su artículo "Dancing links". ^[5]

Por ejemplo, consideremos el problema de cubrir con pentominos un tablero de ajedrez de 8×8 con los 4 cuadrados centrales eliminados:

El problema implica dos tipos de restricciones:

Pentominó: Para cada uno de los 12 pentóminos, existe la restricción de que debe colocarse exactamente una vez. Nombra estas restricciones según los pentóminos correspondientes: FILPNTUVWXY Z. ^[7]

Cuadrado: Para cada uno de los 60 cuadrados, existe la restricción de que debe ser cubierto por un pentominó exactamente una vez. Nombra estas restricciones según los cuadrados correspondientes en el tablero: ij , donde i es la fila y j es la columna.

Por lo tanto, hay 12+60 = 72 restricciones en total.

Como ambos tipos de restricciones son restricciones de exactamente una vez , el problema es un problema de cobertura exacta.

El problema implica muchas opciones, una para cada forma de colocar un pentominó en el tablero. Es conveniente considerar que cada opción satisface un conjunto de 6 restricciones: 1 restricción para el pentominó que se coloca y 5 restricciones para las cinco casillas donde se coloca.

En el caso de un tablero de ajedrez de 8×8 con las 4 casillas centrales eliminadas, hay 1568 opciones de este tipo, por ejemplo:

• {M, 12, 13, 21, 22, 32}
• {M, 13, 14, 22, 23, 33}
• …
• {Yo, 11, 12, 13, 14, 15}
• {Yo, 12, 13, 14, 15, 16}
• …
• {L, 11, 21, 31, 41, 42}
• {L, 12, 22, 32, 42, 43}
• …

Una de las muchas soluciones a este problema de cobertura es el siguiente conjunto de 12 opciones:

• {Yo, 11, 12, 13, 14, 15}
• {N, 16, 26, 27, 37, 47}
• {L, 17, 18, 28, 38, 48}
• {U, 21, 22, 31, 41, 42}
• {X, 23, 32, 33, 34, 43}
• {Miércoles, 24, 25, 35, 36, 46}
• {P, 51, 52, 53, 62, 63}
• {M, 56, 64, 65, 66, 75}
• {Z, 57, 58, 67, 76, 77}
• {T, 61, 71, 72, 73, 81}
• {V, 68, 78, 86, 87, 88}
• {Y, 74, 82, 83, 84, 85}

Este conjunto de opciones corresponde a la siguiente solución al problema de mosaico de pentominós:

Un problema de mosaico de pentominó se ve más naturalmente como un problema de cobertura exacta que como un problema de conjunto de golpes exactos, porque es más natural ver cada elección como un conjunto de restricciones que cada restricción como un conjunto de elecciones.

Cada opción se relaciona con sólo 6 restricciones, que son fáciles de enumerar. Por otro lado, cada restricción se relaciona con muchas opciones, que son más difíciles de enumerar.

Ya sea que se lo considere un problema de cobertura exacta o un problema de conjunto de golpes exactos, la representación matricial es la misma: tiene 1568 filas correspondientes a opciones y 72 columnas correspondientes a restricciones. Cada fila contiene un solo 1 en la columna que identifica el pentominó y cinco 1 en las columnas que identifican los cuadrados cubiertos por el pentominó.

Utilizando la matriz, una computadora puede encontrar todas las soluciones con relativa rapidez, por ejemplo, utilizando Dancing Links .

 Artículos principales: Sudoku , Matemáticas del Sudoku , Algoritmos para resolver el Sudoku

El problema del Sudoku es asignar números (o dígitos, valores, símbolos) a celdas (o cuadrados) de una cuadrícula para satisfacer ciertas restricciones.

En la variante estándar del Sudoku 9×9, hay cuatro tipos de restricciones:

Fila-Columna: Cada intersección de una fila y una columna, es decir, cada celda, debe contener exactamente un número.

Número de fila: cada fila debe contener cada número exactamente una vez

Número de columna: cada columna debe contener cada número exactamente una vez.

Número de caja: Cada caja debe contener cada número exactamente una vez.

Aunque la primera restricción puede parecer trivial, es necesaria para garantizar que solo haya un número por celda. Naturalmente, colocar un número en una celda impide colocar cualquier otro número en la celda que ya está ocupada.

Resolver un sudoku es un problema de cobertura exacta. Más precisamente, resolver un sudoku es un problema de conjunto de aciertos exactos , que es equivalente a un problema de cobertura exacta, cuando se lo considera un problema de selección de posibilidades de modo que cada conjunto de restricciones contenga (es decir, sea alcanzado por) exactamente una posibilidad seleccionada.

Cada posible asignación de un número determinado a una celda determinada es una posibilidad (o candidato). Cuando se juega al sudoku con lápiz y papel, las posibilidades suelen denominarse marcas de lápiz.

En la variante estándar del Sudoku 9×9, en la que a cada una de las 9×9 celdas se le asigna uno de los 9 números, hay 9×9×9=729 posibilidades. Al utilizar una notación obvia para filas, columnas y números, las posibilidades se pueden etiquetar

R1C1#1, R1C1#2, …, R9C9#9.

El hecho de que cada tipo de restricción implique exactamente una de algo es lo que hace que el Sudoku sea un problema de conjunto de resultados exactos. Las restricciones se pueden representar mediante conjuntos de restricciones . El problema consiste en seleccionar posibilidades de modo que cada conjunto de restricciones contenga (es decir, sea afectado por) exactamente una posibilidad seleccionada.

En la variante estándar del Sudoku 9×9, hay cuatro tipos de conjuntos de restricciones correspondientes a los cuatro tipos de restricciones:

Fila-columna: un conjunto de restricciones de fila-columna contiene todas las posibilidades para la intersección de una fila y una columna en particular, es decir, para una celda. Por ejemplo, el conjunto de restricciones para la fila 1 y la columna 1, que se puede etiquetar como R1C1, contiene las 9 posibilidades para la fila 1 y la columna 1, pero con números diferentes:

R1C1 = { R1C1#1, R1C1#2, R1C1#3, R1C1#4, R1C1#5, R1C1#6, R1C1#7, R1C1#8, R1C1#9 }.

Número de fila: un conjunto de restricciones de número de fila contiene todas las posibilidades para una fila y un número en particular. Por ejemplo, el conjunto de restricciones para la fila 1 y el número 1, que se puede etiquetar como R1#1, contiene las 9 posibilidades para la fila 1 y el número 1, pero diferentes columnas:

R1#1 = { R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, R1C9#1 }.

Número de columna: un conjunto de restricciones de número de columna contiene todas las posibilidades para una columna y un número en particular. Por ejemplo, el conjunto de restricciones para la columna 1 y el número 1, que se puede etiquetar como C1#1, contiene las 9 posibilidades para la columna 1 y el número 1, pero diferentes filas:

C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1 }.

Número de casilla: un conjunto de restricciones de número de casilla contiene todas las posibilidades para una casilla y un número en particular. Por ejemplo, el conjunto de restricciones para la casilla 1 (en la esquina superior izquierda) y el número 1, que se puede etiquetar como B1#1, contiene las 9 posibilidades para las celdas de la casilla 1 y el número 1:

B1#1 = { R1C1#1, R1C2#1, R1C3#1, R2C1#1, R2C2#1, R2C3#1, R3C1#1, R3C2#1, R3C3#1 }.

Como hay 9 filas, 9 columnas, 9 casillas y 9 números, hay 9×9=81 conjuntos de restricciones de fila-columna, 9×9=81 conjuntos de restricciones de número de fila, 9×9=81 conjuntos de restricciones de número de columna y 9×9=81 conjuntos de restricciones de número de casilla: 81+81+81+81=324 conjuntos de restricciones en total.

En resumen, la variante estándar del Sudoku 9×9 es un problema de conjunto de aciertos exactos con 729 posibilidades y 324 conjuntos de restricciones. Por lo tanto, el problema se puede representar mediante una matriz de 729×324.

Aunque es difícil presentar la matriz completa de 729×324, la naturaleza general de la matriz se puede ver en varias instantáneas:

La matriz completa de 729×324 está disponible en Robert Hanson. ^[8]

Obsérvese que el conjunto de posibilidades R x C y # z se puede organizar como un cubo de 9 × 9 × 9 en un espacio tridimensional con coordenadas x , y y z . Entonces cada fila R x , columna C y o número # z es una "porción" de posibilidades de 9 × 9 × 1; cada caja B w es un "tubo" de posibilidades de 9 × 3 × 3; cada conjunto de restricciones fila-columna R x C y , conjunto de restricciones número de fila R x # z o conjunto de restricciones número de columna C y # z es una "tira" de posibilidades de 9 × 1 × 1; cada conjunto de restricciones número de caja B w # z es un "cuadrado" de posibilidades de 3 × 3 × 1; y cada posibilidad R x C y # z es un "cubo" de 1 × 1 × 1 que consiste en una única posibilidad. Además, cada conjunto de restricciones o posibilidad es la intersección de los conjuntos componentes. Por ejemplo, R1C2#3 = R1 ∩ C2 ∩ #3, donde ∩ denota intersección de conjuntos.

Aunque otras variantes de Sudoku tienen diferentes cantidades de filas, columnas, números y/o diferentes tipos de restricciones, todas implican posibilidades y conjuntos de restricciones y, por lo tanto, pueden considerarse como problemas de conjuntos de aciertos exactos.

El problema de las N reinas consiste en colocar n reinas de ajedrez en un tablero de ajedrez de n×n de modo que ninguna de ellas se amenace entre sí. Una solución requiere que ninguna de las dos reinas comparta la misma fila, columna o diagonal. Es un ejemplo de un problema de cobertura exacta generalizado. ^[5]

El problema implica cuatro tipos de restricciones:

Rango: Para cada uno de los N rangos, debe haber exactamente una reina.

Archivo: Para cada uno de los N archivos, debe haber exactamente una reina.

Diagonales: Por cada una de las 2 N  − 1 diagonales, debe haber como máximo una reina.

Diagonales inversas: Para cada una de las 2 N  − 1 diagonales inversas, debe haber como máximo una reina.

Nótese que las 2 N filas y columnas forman las restricciones primarias, mientras que las 4 N  − 2 diagonales e inversas diagonales forman las restricciones secundarias. Además, debido a que cada una de las primeras y últimas diagonales e inversas diagonales involucra solo una casilla en el tablero de ajedrez, estas pueden omitirse y, por lo tanto, se puede reducir el número de restricciones secundarias a 4 N  − 6. La matriz para el problema de N reinas tiene entonces N ² filas y 6 N  − 6 columnas, cada fila para una posible ubicación de la reina en cada casilla del tablero de ajedrez y cada columna para cada restricción.

• Problema de satisfacción de restricciones
• Enlaces de baile
• Algoritmo de mapa de diferencias
• Los 21 problemas NP-completos de Karp
• Algoritmo X de Knuth
• Lista de problemas NP-completos
• Partición de un conjunto
• La coincidencia perfecta y la coincidencia tridimensional son casos especiales del problema de la cobertura exacta.

• Implementación de software libre de un solucionador de cobertura exacta en C: utiliza el algoritmo X y enlaces dinámicos. Incluye ejemplos de sudokus y rompecabezas de cuadrícula lógica.
• Solucionador de cobertura exacta en Golang: utiliza el algoritmo X y enlaces danzantes. Incluye ejemplos para sudoku y N reinas.
• Cobertura exacta - Proyecto de referencia de matemáticas