Hispanopedia Wiki
Articulo de referencia

Cobertura exacta

En el campo matemático de la combinatoria , dada una colección S {\displaystyle {\mathcal {S}}} de subconjuntos de un conjunto incógnita {\displaystyle X} , una portada exacta e...

Hispanopedia WikiContenido en espanolLectura gratuita

En el campo matemático de la combinatoria , dada una colecciónS{\displaystyle {\mathcal {S}}}de subconjuntos de un conjuntoincógnita{\displaystyle X}, una portada exacta es una subcolecciónS∗{\displaystyle {\mathcal {S}}^{*}}deS{\displaystyle {\mathcal {S}}}de tal manera que cada elemento enincógnita{\displaystyle X}está contenido en exactamente un subconjunto enS∗{\displaystyle {\mathcal {S}}^{*}}. Se dice que cada elemento enincógnita{\displaystyle X}está cubierto por exactamente un subconjunto enS∗{\displaystyle {\mathcal {S}}^{*}}. [ 1 ] Una cubierta exacta es un tipo de cubierta . En otras palabras,S∗{\displaystyle {\mathcal {S}}^{*}}es una partición deincógnita{\displaystyle X}compuesto por subconjuntos contenidos enS{\displaystyle {\mathcal {S}}}.

El problema de la cobertura exacta para encontrar una cobertura exacta es un tipo de problema de satisfacción de restricciones . Los elementos deS{\displaystyle {\mathcal {S}}}representan opciones y los elementos deincógnita{\displaystyle X}representa restricciones. Es NP-difícil y tiene una variedad de aplicaciones, que van desde la optimización de horarios de vuelos de aerolíneas, computación en la nube y diseño de circuitos electrónicos . [ 2 ]

Un problema de cobertura exacta implica la relación de contención entre subconjuntos y elementos. Sin embargo, 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 colisión exacto , una matriz de incidencia o un grafo bipartito .

En informática , el problema de la cobertura exacta es un problema de decisión para determinar si existe una cobertura exacta. El problema de la 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 como 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 recibe el algoritmo X cuando se implementa de manera eficiente utilizando la técnica Dancing Links de Donald Knuth en una computadora. [ 5 ]

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

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

Definición formal

Dada una colecciónS{\displaystyle {\mathcal {S}}}de subconjuntos de un conjuntoincógnita{\displaystyle X}, una portada exacta deincógnita{\displaystyle X}es una subcolecciónS∗{\displaystyle {\mathcal {S}}^{*}}deS{\displaystyle {\mathcal {S}}}que cumpla dos condiciones:

  • La intersección de cualesquiera dos subconjuntos distintos enS∗{\displaystyle {\mathcal {S}}^{*}}está vacío , es decir, los subconjuntos enS∗{\displaystyle {\mathcal {S}}^{*}}son disjuntos por pares . En otras palabras, cada elemento enincógnita{\displaystyle X}está contenido en como máximo un subconjunto enS∗{\displaystyle {\mathcal {S}}^{*}}.
  • La unión de los subconjuntos enS∗{\displaystyle {\mathcal {S}}^{*}}esincógnita{\displaystyle X}, es decir, los subconjuntos enS∗{\displaystyle {\mathcal {S}}^{*}}cubririncógnita{\displaystyle X}. En otras palabras, cada elemento enincógnita{\displaystyle X}está contenido en al menos un subconjunto enS∗{\displaystyle {\mathcal {S}}^{*}}.

En resumen, una cubierta exacta es exacta en el sentido de que cada elemento enincógnita{\displaystyle X}está contenido en exactamente un subconjunto enS∗{\displaystyle {\mathcal {S}}^{*}}.

De forma equivalente, una cobertura exacta deincógnita{\displaystyle X}es una subcolecciónS∗{\displaystyle {\mathcal {S}}^{*}}deS{\displaystyle {\mathcal {S}}}que particionesincógnita{\displaystyle X}.

Para obtener una cobertura exacta deincógnita{\displaystyle X}Para existir, es necesario que:

  • La unión de los subconjuntos enS{\displaystyle {\mathcal {S}}}esincógnita{\displaystyle X}. En otras palabras, cada elemento enincógnita{\displaystyle X}está contenido en al menos un subconjunto enS{\displaystyle {\mathcal {S}}}.

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

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

Ejemplos básicos

DejarS={norte,O,PAG,mi}{\displaystyle {\mathcal {S}}=\{N,O,P,E\}}ser una colección de subconjuntos de un conjuntoincógnita={1,2,3,4}{\displaystyle X=\{1,2,3,4\}}de tal manera que:

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

La subcolección{O,mi}{\displaystyle \{O,E\}}es una portada exacta deincógnita{\displaystyle X}, ya que los subconjuntosO={1,3}{\displaystyle O=\{1,3\}}ymi={2,4}{\displaystyle E=\{2,4\}}son disjuntos y su unión esincógnita={1,2,3,4}{\displaystyle X=\{1,2,3,4\}}.

La subcolección{norte,O,mi}{\displaystyle \{N,O,E\}}es también una portada exacta deincógnita{\displaystyle X}. Incluyendo el conjunto vacíonorte={}{\displaystyle N=\{\}}No hay diferencia, ya que es disjunto con todos los subconjuntos y no cambia la unión.

La subcolección{mi,PAG}{\displaystyle \{E,P\}}no es una portada exacta deincógnita{\displaystyle X}. Aunque la unión de los subconjuntosmi{\displaystyle E}yPAG{\displaystyle P}es{1,2,3,4}=incógnita{\displaystyle \{1,2,3,4\}=X}, la intersección de los subconjuntosmi{\displaystyle E}yPAG{\displaystyle P},{2}{\displaystyle \{2\}}, no está vacío. Por lo tanto, los subconjuntosmi{\displaystyle E}yPAG{\displaystyle P}no cumplen con el requisito disjunto de una cobertura exacta.

La subcolección{norte,PAG}{\displaystyle \{N,P\}}tampoco es una cobertura exacta deincógnita{\displaystyle X}. A pesar denorte{\displaystyle N}yPAG{\displaystyle P}son disjuntos, su unión no esincógnita{\displaystyle X}, por lo que no cumplen con el requisito de cobertura .

Por otro lado, no hay una cobertura exacta —de hecho, ni siquiera una cobertura— deY={1,2,3,4,5}{\displaystyle Y=\{1,2,3,4,5\}}porque⋃S={1,2,3,4}{\displaystyle \bigcup {\mathcal {S}}=\{1,2,3,4\}}es un subconjunto propio deY{\displaystyle Y}: Ninguno de los subconjuntos enS{\displaystyle {\mathcal {S}}}contiene el elemento 5.

Ejemplo detallado

Imagen del ejemplo detallado.

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 lo demuestra el siguiente argumento: Dado 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 ninguna cobertura exacta que contenga A .

Por otro lado, si una cobertura exacta contiene B , entonces no contiene A ni C , ya que cada uno de estos subconjuntos tiene en común con B el elemento 1 o el 4. Dado que D es el único subconjunto restante que contiene el elemento 5, D debe formar parte de la cobertura exacta. Si una cobertura exacta contiene D , entonces no contiene E , ya que E tiene en común con D los elementos 3 y 6. Por lo tanto , F es el único subconjunto restante, y la subcolección { B , D , F } es, en efecto, una cobertura exacta. Consulte el ejemplo en el artículo sobre el algoritmo X de Knuth para una versión de este argumento basada en matrices.

Representaciones

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 en 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é relacionado R T con exactamente un elemento en S * . Aquí R T es el recíproco de R .

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

Las representaciones de un problema de cobertura exacta incluyen un problema de conjunto de colisión exacto, una matriz de incidencia y un grafo bipartito.

Conjunto de bateo exacto

En matemáticas , dado un conjunto S y una colección X de subconjuntos de S , un conjunto de colisión exacto S * es un subconjunto de S tal que cada subconjunto en X contiene exactamente un elemento en S * . Se dice que cada subconjunto en X es colisionado por exactamente un elemento en S * .

El problema del conjunto de colisión exacto 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:

  • I = { 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 colisión exacto, ya que cada subconjunto en X es alcanzado por (contiene) exactamente un elemento en S * , como lo deja claro el resaltado.

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

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

Matriz de incidencia

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

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

En la representación matricial, una cobertura exacta es una selección de filas tal que cada columna contiene un 1 en exactamente una fila seleccionada. Cada fila representa una elecció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 del artículo sobre el algoritmo X de Knuth para obtener una solución basada en matrices al ejemplo detallado anterior.

Hipergrafo

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

Grafo bipartito

La relación contiene puede representarse mediante un grafo bipartito .

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

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

Por ejemplo, la relación contenida en el ejemplo detallado anterior puede representarse mediante un grafo 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 a exactamente un vértice seleccionado, como lo deja claro el resaltado.

Encontrar soluciones

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

Cuando el algoritmo X se implementa de manera eficiente en una computadora utilizando la técnica de enlaces danzantes de Donald Knuth , Knuth lo denomina 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. Dado 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. DLX utiliza entonces la técnica de enlaces danzantes para seleccionar rápidamente permutaciones de filas como posibles soluciones y para retroceder (deshacer) eficientemente las suposiciones erróneas. [ 5 ]

Cobertura exacta generalizada

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

Como explica Knuth, un problema de cobertura exacta generalizado puede convertirse en un problema de cobertura exacta equivalente simplemente agregando una fila por cada columna secundaria, que contenga un solo 1 en dicha columna. [ 6 ] Si en una solución candidata particular se cumple una columna secundaria específica, entonces no es necesaria la fila agregada. Pero si la columna secundaria no se cumple, como se permite en el problema generalizado pero no en el problema estándar, entonces se puede seleccionar la fila agregada para asegurar que la columna se cumpla.

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 número máximo de reinas en lugar de un número exacto.

Ejemplos destacables

Debido a su NP-completitud, 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 conocidos, la reducción es particularmente directa. Por ejemplo, el problema de cubrir un tablero con pentominós y la resolución de Sudoku pueden considerarse problemas de cobertura exacta.

Teselado de pentominós

El problema de cubrir un tablero de 60 casillas 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 pentominós un tablero de ajedrez de 8×8 al que se le han quitado las 4 casillas centrales:

El problema implica dos tipos de restricciones:

Pentominó: Para cada uno de los 12 pentominós, existe la restricción de que debe colocarse exactamente una vez. Nombra estas restricciones según los pentominós correspondientes: FILPNTUVWXY Z. [ 7 ]
Casilla: Para cada una de las 60 casillas, existe la restricción de que debe estar cubierta por un pentominó exactamente una vez. Nombra estas restricciones según las casillas 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.

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

El problema implica varias 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:

  • {F, 12, 13, 21, 22, 32}
  • {F, 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}
  • {W, 24, 25, 35, 36, 46}
  • {P, 51, 52, 53, 62, 63}
  • {F, 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 del recubrimiento con pentominós:

Un problema de recubrimiento con pentominós se percibe de forma más natural como un problema de cobertura exacta que como un problema de conjunto de colisión exacto, 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 solo 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 considere como un problema de cobertura exacta o un problema de conjunto de colisión exacto, la representación matricial es la misma: 1568 filas que corresponden a las opciones y 72 columnas que corresponden a las restricciones. Cada fila contiene un 1 en la columna que identifica el pentominó y cinco 1 en las columnas que identifican las casillas cubiertas por el pentominó.

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

Sudoku

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

El problema en el Sudoku consiste en asignar números (o dígitos, valores, símbolos) a las celdas (o cuadrados) de una cuadrícula de manera que se cumplan ciertas restricciones.

En la variante estándar de Sudoku de 9×9, existen 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 pueda 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 ahora ocupa.

Resolver Sudoku es un problema de cobertura exacta. Más precisamente, resolver Sudoku es un problema de conjunto de colisión exacto , que es equivalente a un problema de cobertura exacta, cuando se considera como un problema para seleccionar posibilidades de tal manera que cada conjunto de restricciones contenga (es decir, sea alcanzado por) exactamente una posibilidad seleccionada.

Cada posible asignación de un número a una celda específica es una posibilidad (o candidata). Cuando se juega al Sudoku con lápiz y papel, las posibilidades suelen denominarse marcas de lápiz.

En la variante estándar de Sudoku 9×9, en la que a cada una de las 9×9 celdas se le asigna uno de 9 números, hay 9×9×9=729 posibilidades. Usando 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 sola opción es lo que convierte al Sudoku en un problema de conjuntos de coincidencias exactas. Las restricciones se pueden representar mediante conjuntos de restricciones . El problema consiste en seleccionar posibilidades de tal manera que cada conjunto de restricciones contenga (es decir, sea alcanzado por) exactamente una posibilidad seleccionada.

En la variante estándar de Sudoku 9×9, existen cuatro tipos de conjuntos de restricciones que corresponden 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 específicas, 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 }.
Fila-Número: Un conjunto de restricciones de fila-número contiene todas las posibilidades para una fila y un número determinados. 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 en columnas diferentes:
R1#1 = { R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, R1C9#1 }.
Conjunto de restricciones de número de columna: Un conjunto de restricciones de número de columna contiene todas las posibilidades para una columna y un número específicos. 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 en filas diferentes:
C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1 }.
Número de caja: Un conjunto de restricciones de número de caja contiene todas las posibilidades para una caja y un número específicos. Por ejemplo, el conjunto de restricciones para la caja 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 en la caja 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 }.

Dado que 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 de Sudoku de 9×9 es un problema de conjunto de coincidencias exactas 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 apreciar en varias instantáneas:

La matriz completa de 729×324 está disponible a través de Robert Hanson. [ 8 ]

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 "rebanada" de posibilidades de 9×9×1; cada caja B w es un "tubo" de posibilidades de 9×3×3; cada conjunto de restricciones de fila-columna R x C y , conjunto de restricciones de número de fila R x # z , o conjunto de restricciones de número de columna C y # z es una "franja" de posibilidades de 9×1×1; cada conjunto de restricciones de 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 "cubito" de 1×1×1 que consiste en una sola 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 la intersección de conjuntos.

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

Problema de las N reinas

El problema de las N reinas consiste en colocar n reinas de ajedrez en un tablero de n × n de manera que ninguna reina amenace a otra. Una solución requiere que ninguna reina comparta la misma fila, columna o diagonal. Es un ejemplo de un problema de cobertura exacta generalizado . [ 5 ]

La única solución simétrica al rompecabezas de las ocho reinas ( salvo rotación y reflexión ).

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: En 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.

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

Véase también

Referencias

  1. ^ Resolución de instancias de cobertura exactas con biocomputación basada en red impulsada por motores moleculares Pradheebha Surendiran, Christoph Robert Meinecke, Aseem Salhotra, Georg Heldt, Jingyuan Zhu, Alf Månsson, Stefan Diez, Danny Reuter, Hillel Kugler, Heiner Linke y Till Korten 2022 2 (5), 396-403 DOI: 10.1021/acsnanoscienceau.2c00013
  2. ^ Korten, hasta; Díez, Stefan; Linke, Heiner; Nicolau, Dan V; Kugler, Hillel (1 de agosto de 2021). "Diseño de circuitos de biocomputación basados ​​en red para el problema de cobertura exacta" . Nueva Revista de Física . 23 (8): 085004. Código bibliográfico : 2021NJPh...23h5004K . doi : 10.1088/1367-2630/ac175d . ISSN 1367-2630 . 
  3. 1 2 M.R. Garey ; DS Johnson (1979). Computadoras e intratabilidad: Una guía a la teoría de la NP-completitud . Nueva York: WH Freeman. ISBN 0-7167-1045-5. Este libro es un clásico que desarrolla la teoría y luego cataloga muchos problemas NP-completos.
  4. ↑ Richard M. Karp (1972). "Reducibilidad entre problemas combinatorios" (PDF) . En RE Miller; JW Thatcher (eds.). Complejidad de los cálculos informáticos . Actas de un simposio sobre la complejidad de los cálculos informáticos. Nueva York: Plenum. págs. 85–103 . ISBN  0-3063-0707-3. Archivado del original (PDF) el 29-06-2011 . Consultado el 27-06-2008 .
  5. 1 2 3 4 5 Knuth, Donald (2000). "Dancing links". arXiv : cs/0011047 .
  6. ↑ Donald Knuth explica esta sencilla generalización en su artículo "Dancing Links", en particular, al explicar los problemas del tetrastick y de las N reinas .
  7. ↑ Golomb, Solomon W. (1994). Poliominós: Rompecabezas, patrones, problemas y empaquetamientos (2.ª ed.). Princeton, Nueva Jersey: Princeton University Press. pág . 7. ISBN   0-691-02444-8.
  8. ↑ Hanson, Robert M. "Problema de cobertura exacta" . www.stolaf.edu . St. Olaf College . Consultado el 20 de agosto de 2020 .
  • Implementación de software libre en C para resolver problemas de cobertura exacta . Utiliza el algoritmo X y el algoritmo Dancing Links. Incluye ejemplos para Sudoku y rompecabezas de lógica.
  • Solucionador de cobertura exacta en Golang : utiliza el algoritmo X y Dancing Links. Incluye ejemplos para Sudoku y N reinas.
  • Portada exacta - Proyecto de Referencia Matemática
  • El formato DLX es utilizado por varios solucionadores para leer problemas de cobertura exacta (en color).
  • Miniexact es una implementación en C eficiente y sin dependencias del algoritmo DLX, compatible con los algoritmos X, C (colores), M (multiplicidades) y, de forma preliminar, $ (coste mínimo). Lee el formato DLX, varias de sus extensiones y proporciona un módulo para Python. Se puede instalar desde PyPI en diversas plataformas.