En matemáticas , dada una colección S de subconjuntos de un conjunto X , una cubierta exacta es una subcolección S * de S, de modo que cada elemento en X está contenido exactamente en un subconjunto en S * . Uno dice que cada elemento en X está cubierto por exactamente un subconjunto en S * . Una cubierta exacta es una especie de cubierta .
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-complete [1] y es uno de los 21 problemas de Karp NP-complete . [2] El problema exacto de cobertura es un tipo de problema de satisfacción de restricciones .
Un problema de cobertura exacto puede representarse mediante una matriz de incidencia o un gráfico bipartito .
El algoritmo X de Knuth es un algoritmo que encuentra todas las soluciones a un problema de cobertura exacto. DLX es el nombre dado a Algoritmo X cuando se lleva a cabo de manera eficiente el uso de Donald Knuth 's Baile Enlaces técnica en un ordenador. [3]
El problema de la cobertura exacta estándar se puede generalizar levemente para involucrar no solo "exactamente una" restricción sino también "como máximo una" restricción.
Encontrar inclinaciones Pentomino y resolver Sudoku son ejemplos notables de problemas de cobertura exactos. El problema de las reinas n es un problema de cobertura exacta ligeramente generalizado.
Definición formal [ editar ]
Dada una colección S de subconjuntos de un conjunto X , una cubierta exacta de X es una subcolección S * de S que cumple dos condiciones:
- La intersección de dos subconjuntos distintos en S * está vacía , es decir, los subconjuntos en S * están separados por pares . En otras palabras, cada elemento en X está contenido como máximo en un subconjunto en S * .
- La unión de los subconjuntos en S * es X , es decir, los subconjuntos en S * cubierta X . En otras palabras, cada elemento en X está contenido en al menos un subconjunto en S * .
En resumen, una cubierta exacta es "exacta" en el sentido de que cada elemento en X está contenido exactamente en un subconjunto en S * .
Para que exista una cobertura exacta de X , es necesario que:
- La unión de los subconjuntos de S es X . En otras palabras, cada elemento en X está contenido en al menos un subconjunto de S .
Si el conjunto vacío ∅ está contenido en 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á en S * . En otras palabras, cada subconjunto en S * contiene al menos un elemento.
Ejemplos básicos [ editar ]
Sea S = { N , O , P , E } una colección de subconjuntos de un conjunto X = {1, 2, 3, 4} de manera que:
- N = {},
- O = {1, 3},
- P = {2, 3} y
- E = {2, 4}.
La subcolección { O , E } es una cobertura exacta de X , ya que los subconjuntos O = {1, 3} y E = {2, 4} son disjuntos y su unión es X = {1, 2, 3, 4}.
El subcolección { N , O , E } es también una cobertura exacta de X . La inclusión del conjunto vacío N = {} no hace ninguna diferencia, ya que es disjunta con todos los subconjuntos y no cambia la unión.
La subcolección { E , P } no es una cobertura exacta de X . La intersección de los subconjuntos E y P , {2}, no está vacía: los subconjuntos E y P no son disjuntos. Además, la unión de los subconjuntos E y P , {2, 3, 4}, no es X = {1, 2, 3, 4}: ni E ni P cubren el elemento 1.
Por otro lado, no hay una cobertura exacta —de hecho, ni siquiera una cobertura— de Y = {1, 2, 3, 4, 5} porquees un subconjunto apropiado de Y : ninguno de los subconjuntos en S contiene el elemento 5.
Ejemplo detallado [ editar ]
Sea S = { A , B , C , D , E , F } una colección de subconjuntos de un conjunto X = {1, 2, 3, 4, 5, 6, 7} de manera 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}.
Entonces la subcolección S * = { B , D , F } es una cubierta exacta, ya que cada elemento en X está contenido exactamente en uno de los subconjuntos:
- B = {1, 4};
- D = {3, 5, 6}; o
- F = {2, 7}.
Además, { B , D , F } es la única cobertura exacta, como lo demuestra el siguiente argumento: Debido a que A y B son los únicos subconjuntos que contienen 1, una cubierta exacta debe contener A o B , pero no ambos. Si una cobertura exacta contiene A , entonces no contiene B , C , E , o F , como cada uno de estos subconjuntos tiene un elemento en común con A . Entonces D es el único subconjunto restante, pero la colección { A , D} No cubrir el elemento 2. En conclusión, no hay cobertura exacta que contiene una . Por otro lado, si una cobertura exacta contiene B , entonces no contener A o C , como cada uno de estos subconjuntos tiene un elemento en común con B . Debido a que D es el único subconjunto restante que contiene 5, D debe ser parte de la cubierta exacta. Si una cobertura exacta contiene D , entonces no contener E , ya que E tiene un elemento en común con D . Entonces F es el único subconjunto restante, y la colección { B , D , F} es de hecho una cubierta exacta. Vea el ejemplo en el artículo sobre el Algoritmo X de Knuth para obtener una versión matricial de este argumento.
Representaciones [ editar ]
Un problema de cobertura exacta se define por la relación binaria "contiene" entre subconjuntos en S y elementos en X . Hay diferentes formas equivalentes para representar esta relación.
Representación estándar [ editar ]
La forma estándar de representar la relación "contiene" es enumerar los elementos en cada subconjunto.
- A = {1, 4, 7};
- B = { 1 , 4 };
- C = {4, 5, 7};
- D = { 3 , 5 , 6 };
- E = {2, 3, 6, 7}; y
- F = { 2 , 7 }.
Nuevamente, la subcolección S * = { B , D , F } es una cubierta exacta, ya que cada elemento está contenido exactamente en un subconjunto seleccionado, como lo resalta el resaltado.
Representación inversa [ editar ]
La relación "contiene" entre subconjuntos y elementos puede convertirse , enumerando los subconjuntos en los que está contenido cada elemento.
Por ejemplo, la relación "contiene" en el ejemplo detallado anterior puede representarse enumerando los subconjuntos en los que está contenido cada elemento:
- 1 es un elemento de A , B ;
- 2 es un elemento de E , F ;
- 3 es un elemento de D , E ;
- 4 es un elemento de A , B , C ;
- 5 es un elemento de C , D ;
- 6 es un elemento de D , E ; y
- 7 es un elemento de A , C , E , F .
Nuevamente, la subcolección S * = { B , D , F } es una cubierta exacta, ya que cada elemento está contenido exactamente en un subconjunto seleccionado, como lo resalta el resaltado.
Al resolver un problema de cobertura exacto, a menudo es útil cambiar entre las representaciones estándar e inversa.
Representaciones matriciales e hipergráficas [ editar ]
La matriz incluye una fila para cada subconjunto en S y una columna para cada elemento en 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. Como cada fila representa los elementos contenidos en el subconjunto correspondiente y cada columna representa los subconjuntos que contienen el elemento correspondiente, una matriz de incidencia proporciona efectivamente las representaciones estándar e inversa.
En la representación matricial, una cubierta exacta es una selección de filas de modo que cada columna contenga un 1 en exactamente una fila seleccionada.
Por ejemplo, la relación "contiene" en el ejemplo detallado anterior se puede representar mediante una matriz de incidencia de 6 × 7: [4]
1 2 3 4 4 5 5 6 6 7 7 UNA 1 0 0 0 0 1 0 0 0 0 1 si 1 0 0 0 0 1 0 0 0 0 0 0 do 0 0 0 0 0 0 1 1 0 0 1 re 0 0 0 0 1 0 0 1 1 0 0 mi 0 0 1 1 0 0 0 0 1 1 F 0 0 1 0 0 0 0 0 0 0 0 1
Nuevamente, la subcolección S * = { B , D , F } es una cubierta exacta, ya que cada elemento está contenido exactamente en un subconjunto seleccionado, es decir, cada columna contiene un 1 en exactamente una fila seleccionada, como lo resalta el resaltado.
Vea el ejemplo en el artículo sobre el Algoritmo X de Knuth para una solución basada en matriz para el ejemplo detallado anterior.
A su vez, la matriz de incidencia también puede verse como una descripción de una hipergrafía . La hipergrafía incluye un nodo para cada elemento en X y un borde para cada subconjunto en S ; cada nodo está incluido exactamente en uno de los bordes que forman la cubierta.
Representación gráfica [ editar ]
Los vértices de la gráfica 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, un borde conecta los vértices correspondientes en el gráfico.
En la representación gráfica, una cubierta exacta es una selección de vértices correspondientes a subconjuntos de modo que cada vértice correspondiente a un elemento esté conectado exactamente a un vértice seleccionado.
Por ejemplo, la relación "contiene" en el ejemplo detallado arriba se puede representar mediante un gráfico bipartito con 6 + 7 = 13 vértices:
Nuevamente, la subcolección S * = { B , D , F } es una cubierta exacta, ya que cada elemento está contenido exactamente en un subconjunto seleccionado, es decir, el vértice correspondiente a cada elemento en X está conectado exactamente a un vértice seleccionado, ya que destacando deja en claro.
Problemas equivalentes [ editar ]
Aunque el problema de cobertura exacta canónica involucra una colección S de subconjuntos de un conjunto X , la lógica no depende de la presencia de subconjuntos que contengan elementos. Un "problema de cobertura exacto abstracto" surge cuando hay una relación heterogénea entre dos conjuntos P y Q y el objetivo es seleccionar un subconjunto P * de P de modo que cada elemento en Q esté relacionado exactamente con un elemento en P * . En general, los elementos de P representan elecciones y los elementos de Q representan restricciones "exactamente una" sobre esas elecciones.
Más formalmente, dada una relación binaria R ⊆ P × Q entre los conjuntos P y Q , se puede llamar a un subconjunto P * de P una "cobertura exacta abstracta" de Q si cada elemento en Q está relacionado con R T a exactamente un elemento en P * . Aquí R T es la inversa de R .
En general, R T restringido a Q × P * es una función de Q a P * , que mapea cada elemento de Q al elemento único en P * que es R relacionados con la PI a ese elemento en Q . Esta función es en , a menos que P * contiene el "conjunto vacío", es decir, un elemento que no es R relacionados con la PI a cualquier elemento en Q .
En el problema de cobertura exacta canónica, P es una colección S de subconjuntos de X , Q es el conjunto X , R es la relación binaria "contiene" entre subconjuntos y elementos, y R T restringido a Q × P * es la función "es contenido en "desde elementos a subconjuntos seleccionados.
Juego de golpes exactos [ editar ]
En matemáticas , dada una colección S de subconjuntos de un conjunto X , un conjunto de golpes exactos X * es un subconjunto de X de tal manera que cada subconjunto en S contiene exactamente un elemento en X * . Uno dice que cada subconjunto en S es golpeado por exactamente un elemento en X * .
En informática , el problema exacto del conjunto de bateo es un problema de decisión para encontrar un conjunto de bateo exacto o determinar si no existe ninguno.
El problema exacto del conjunto de golpes es un problema abstracto de cobertura exacta. En la notación anterior , P es el conjunto X , Q es una colección S de subconjuntos de X , R es la relación binaria "está contenida en" entre elementos y subconjuntos, y R −1 restringido a Q × P * es la función " contiene "de subconjuntos a elementos seleccionados.
Mientras que un problema de cobertura exacto implica seleccionar subconjuntos y la relación "contiene" de subconjuntos a elementos, un problema de conjunto de golpes exactos implica seleccionar elementos y la relación "está contenida en" de elementos a subconjuntos. En cierto sentido, un problema de conjunto de golpes exactos es el inverso del problema de cobertura exacto que involucra el mismo conjunto y colección de subconjuntos.
Ejemplo de conjunto de golpes exactos [ editar ]
Como en el ejemplo detallado de la cubierta exacta anterior, dejemos que S = { A , B , C , D , E , F } sea una colección de subconjuntos de un conjunto X = {1, 2, 3, 4, 5, 6, 7} tal 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}.
Entonces X * = {1, 2, 5} es un conjunto de golpes exactos, ya que cada subconjunto en S contiene exactamente un elemento en X * , como lo resalta el resaltado.
Además, {1, 2, 5} es el único conjunto de bateo exacto, como lo demuestra el siguiente argumento: dado que 2 y 7 son los únicos elementos que golpean F , un conjunto de bateo exacto debe contener 2 o 7, pero no ambos. Si un conjunto de bateo exacto contiene 7, entonces no contiene 1, 2, 3, 4, 5 o 6, ya que cada uno de estos elementos está contenido en algún subconjunto que también contiene 7. Entonces no quedan más elementos, pero {7} no es exactamente un conjunto de golpear, ya que no golpea B o D . En conclusión, no hay un conjunto de bateo exacto que contenga 7. Por otro lado, si un conjunto de bateo exacto contiene 2, entonces no contiene 3, 6 o 7, ya que cada uno de estos elementos está contenido en algún subconjunto que también contiene 2. Porque 5 es el único elemento restante que golpea D, El conjunto exacto de golpear debe contener 5. Si un conjunto de bateo exacta contiene 5, a continuación, que no contiene 4, ya que tanto éxito C . Debido a que 1 es el único elemento restante que golpea A , el conjunto de bateo exacto debe contener 1. Entonces no quedan más elementos restantes, y {1, 2, 5} es de hecho un conjunto de bateo exacto.
Aunque este ejemplo involucra la misma colección de subconjuntos que el ejemplo de portada exacto detallado anteriormente, es esencialmente un problema diferente. En cierto sentido, el problema exacto del conjunto de golpes es el inverso (o transponer o conversar) del problema de cobertura exacto correspondiente anterior, como la representación de la matriz deja en claro:
UNA si do re mi F 1 1 1 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 1 3 0 0 0 0 0 0 1 1 0 0 4 4 1 1 1 0 0 0 0 0 0 5 5 0 0 0 0 1 1 0 0 0 0 6 6 0 0 0 0 0 0 1 1 0 0 7 7 1 0 0 1 0 0 1 1
Ejemplo dual [ editar ]
Pero hay otro problema de conjunto de golpes exactos que es esencialmente el mismo que el ejemplo detallado de la cubierta exacta anterior, en el que los elementos numerados se convierten en subconjuntos y los subconjuntos con letras se convierten en elementos, invirtiendo efectivamente la relación entre subconjuntos y elemento.
Por ejemplo, como el subconjunto B contiene los elementos 1 y 4 en el problema de cobertura exacta, los subconjuntos I y IV contienen el elemento b en el problema del conjunto de doble golpe exacto.
En particular, que S = { I , II , III , IV , V , VI , VII } sea una colección de subconjuntos de un conjunto X = { a , b , c , d , e , f } de modo 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 X * = { b , d , f } es un conjunto de golpes exactos, ya que cada subconjunto en S contiene (es golpeado por) exactamente un elemento en X * , como lo resalta el resaltado.
El conjunto de golpes exactos X * = { b , d , f } aquí es esencialmente el mismo que el de la cubierta exacta S * = { B , D , F } anterior, como la representación de la matriz deja en claro:
yo II III IV V VI VII una 1 0 0 0 0 1 0 0 0 0 1 si 1 0 0 0 0 1 0 0 0 0 0 0 do 0 0 0 0 0 0 1 1 0 0 1 re 0 0 0 0 1 0 0 1 1 0 0 mi 0 0 1 1 0 0 0 0 1 1 F 0 0 1 0 0 0 0 0 0 0 0 1
Encontrar soluciones [ editar ]
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 cobertura exacto. [3] Técnicamente, el algoritmo X es un recursivo , no determinista , primero en profundidad , dando marcha atrás algoritmo .
Cuando Algoritmo X se lleva a cabo de manera eficiente el uso de Donald Knuth 's Baile Enlaces técnica en una computadora, Knuth llama DLX. DLX utiliza la representación matricial del problema, implementada como una serie de listas doblemente vinculadas de los 1s de la matriz: cada 1 elemento tiene un enlace al siguiente 1 arriba, abajo, a la izquierda y a la derecha de sí mismo. (Técnicamente, debido a que las listas son circulares, esto forma un toro). Debido a que los problemas de cobertura exactos tienden a ser escasos, 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 las permutaciones de filas como posibles soluciones y para dar marcha atrás (deshacer) conjeturas erróneas de manera eficiente. [3]
Generalizaciones [ editar ]
En un problema de cobertura exacto estándar, cada restricción debe cumplirse exactamente una vez. Es una generalización simple relajar un poco este requisito y permitir la posibilidad de que algunas restricciones "primarias" deben cumplirse exactamente con una selección, pero otras restricciones "secundarias" pueden satisfacerse como máximo con una selección.
Como explica Knuth, un problema de cobertura exacto generalizado se puede convertir en un problema de cobertura exacto equivalente simplemente agregando una fila para cada columna secundaria, que contiene un solo 1 en esa columna. [5] Si en una solución candidata particular se satisface una columna secundaria particular, entonces la fila agregada no es necesaria. Pero si la columna secundaria no está satisfecha, como se permite en el problema generalizado pero no en el problema estándar, la fila agregada se puede seleccionar para garantizar que la columna esté satisfecha.
Pero Knuth continúa explicando que es mejor trabajar directamente con el problema generalizado, porque el algoritmo generalizado es más simple y más rápido: un simple cambio en su Algoritmo X permite que las columnas secundarias se manejen directamente.
El problema de N reinas es un ejemplo de un problema de cobertura exacto generalizado, ya que las restricciones correspondientes a las diagonales del tablero de ajedrez tienen un recuento de reina máximo en lugar de exacto.
Ejemplos notables [ editar ]
Debido a su integridad de NP, cualquier problema en NP puede reducirse a problemas de cobertura exactos, 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 un tablero con pentominoes y resolver Sudoku puede verse como un problema de cobertura exacto.
Azulejos Pentomino [ editar ]
El problema de colocar en mosaico un tablero de 60 cuadrados con los 12 pentominoes libres diferentes es un ejemplo de un problema de cobertura exacto, como explica Donald Knuth en su artículo "Dancing links". [3]
Por ejemplo, considere el problema de mosaico con pentominoes en un tablero de ajedrez de 8 × 8 con los 4 cuadrados centrales eliminados:
11 12 13 14 15 dieciséis 17 18 años 21 22 23 24 25 26 27 28 31 32 33 34 35 36 37 38 41 42 43 46 47 48 51 52 53 56 57 58 61 62 63 64 sesenta y cinco 66 67 68 71 72 73 74 75 76 77 78 81 82 83 84 85 86 87 88
El problema involucra dos tipos de restricciones:
- Pentomino: para cada uno de los 12 pentominoes, existe la restricción de que debe colocarse exactamente una vez. Nombre estas restricciones después de los pentominoes correspondientes: FILPNTUVWXY Z. [6]
- Cuadrado: para cada uno de los 60 cuadrados, existe la restricción de que debe estar cubierto por un pentomino exactamente una vez. Nombra estas restricciones después de los cuadrados correspondientes en el tablero: ij , donde i es el rango y j es el archivo.
Por lo tanto, hay 12 + 60 = 72 restricciones en total.
Como ambos tipos de restricciones son "exactamente una", el problema es un problema de cobertura exacta.
El problema involucra muchas opciones, una para cada forma de colocar un pentomino en el tablero. Es conveniente considerar que cada opción satisface un conjunto de 6 restricciones: 1 restricción para el pentomino que se coloca y 5 restricciones para los cinco cuadrados donde se coloca.
En el caso de un tablero de ajedrez de 8 × 8 con los 4 cuadrados centrales eliminados, hay 1568 opciones, por ejemplo:
- {F, 12, 13, 21, 22, 32}
- {F, 13, 14, 22, 23, 33}
- ...
- {I, 11, 12, 13, 14, 15}
- {I, 12, 13, 14, 15, 16}
- ...
- {L, 11, 21, 31, 41, 42}
- {L, 12, 22, 32, 42, 43}
- ...
Una de las muchas soluciones de este problema de cobertura exacta es el siguiente conjunto de 12 opciones:
- {I, 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 de mosaico de pentomino:
Un problema de mosaico de pentomino se ve más naturalmente como un problema de cobertura exacta que un problema de conjunto de golpes exactos, porque es más natural ver cada opción como un conjunto de restricciones que cada restricción como un conjunto de opciones.
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 vea como un problema de cobertura exacto o un problema de conjunto de golpes exactos, la representación matricial es la misma, con 1568 filas correspondientes a opciones y 72 columnas correspondientes a restricciones. Cada fila contiene un solo 1 en la columna que identifica el pentomino y cinco 1 en las columnas que identifican los cuadrados cubiertos por el pentomino.
Usando la matriz, una computadora puede encontrar todas las soluciones relativamente rápido, por ejemplo, usando Dancing Links .
Sudoku [ editar ]
El problema en Sudoku es asignar números (o dígitos, valores, símbolos) a las celdas (o cuadrados) en una cuadrícula para satisfacer ciertas restricciones.
En la variante estándar de Sudoku 9 × 9, hay cuatro tipos de restricciones:
- Fila-Columna: cada intersección de una fila y 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.
Si bien la primera restricción puede parecer trivial, sin embargo, es necesaria para garantizar que solo haya un número por celda. Intuitivamente, colocar un número en una celda prohíbe colocar ese número en cualquier otra celda que comparta la misma columna, fila o cuadro y también prohíbe colocar cualquier otro número en la celda ahora ocupada.
Resolver Sudoku es un problema de cobertura exacto.
Más precisamente, resolver Sudoku es un problema de conjunto de golpes exactos , que es equivalente a un problema de cobertura exacto, cuando se ve como un problema para seleccionar posibilidades de manera que cada conjunto de restricciones contenga (es decir, sea golpeado) exactamente una posibilidad seleccionada. En la notación anterior para el problema de cobertura exacto (generalizado), X es el conjunto de posibilidades, Y es un conjunto de conjuntos de restricciones y R es la relación binaria "está contenida".
Cada posible asignación de un número particular a una celda particular es una posibilidad (o candidato). Cuando el Sudoku se juega con lápiz y papel, las posibilidades a menudo se llaman marcas de lápiz.
En la variante estándar de Sudoku 9 × 9, en la que a cada una de las celdas 9 × 9 se le asigna uno de los 9 números, hay 9 × 9 × 9 = 729 posibilidades. Usando 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 uno de algo es lo que hace que Sudoku sea un problema exacto. Las restricciones se pueden representar mediante conjuntos de restricciones . El problema es seleccionar posibilidades de 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, 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 columna en particular, es decir, para una celda. Por ejemplo, la restricción establecida para la fila 1 y la columna 1, que puede etiquetarse como R1C1, contiene las 9 posibilidades para la fila 1 y la columna 1 pero diferentes números:
- 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 número en particular. Por ejemplo, la restricción establecida para la fila 1 y el número 1, que puede etiquetarse 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 número en particular. Por ejemplo, la restricción establecida para la columna 1 y el número 1, que puede etiquetarse 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 cuadro : un conjunto de restricciones de número de cuadro contiene todas las posibilidades para un cuadro y número en particular. Por ejemplo, la restricción establecida para el cuadro 1 (en la esquina superior izquierda) y el número 1, que puede etiquetarse como B1 # 1, contiene las 9 posibilidades para las celdas en el cuadro 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 cuadros y 9 números, hay 9 × 9 = 81 conjuntos de restricción de fila-columna, 9 × 9 = 81 conjuntos de restricción de número de fila, 9 × 9 = 81 conjuntos de restricción de número de columna, y 9 × 9 = 81 conjuntos de restricciones de número de caja: 81 + 81 + 81 + 81 = 324 conjuntos de restricciones en total.
En resumen, la variante estándar Sudoku 9 × 9 es un problema de conjunto de golpes exactos con 729 posibilidades y 324 conjuntos de restricciones. Así, el problema puede ser representado por 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:
|
|
|
|
Tenga en cuenta 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 9 × 9 × 1; cada caja B w es un "tubo" de posibilidades de 9x3 × 3; cada conjunto de restricciones fila-columna R x C y , conjunto de restricciones número-fila R x # z , o conjunto de restricciones número-columna C y # z es una "tira" de posibilidades 9x1 × 1; cada conjunto de restricciones de número de caja Bw # z es un "cuadrado" de posibilidades de 3x3 × 1; y cada posibilidad R x C y # z es un "cubito" 1x1 × 1 que consiste en una sola posibilidad. Además, cada conjunto de restricciones o posibilidad es la intersección de los conjuntos de componentes. Por ejemplo, R1C2 # 3 = R1 ∩ C2 ∩ # 3, donde ∩ denota la intersección establecida.
Aunque otras variaciones de Sudoku tienen diferentes números de filas, columnas, números y / o diferentes tipos de restricciones, todas implican posibilidades y conjuntos de restricciones y, por lo tanto, pueden verse como problemas de conjunto de golpes exactos.
Problema de N reinas [ editar ]
![[icono]](https://en.wikipedia.org/wiki/File:Wiki_letter_w_cropped.svg){kind=small}
El problema de las reinas N es un ejemplo de un problema de cobertura exacto generalizado. [3] El problema involucra 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: para 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.
Tenga en cuenta que las restricciones de rango y archivo 2 N forman las restricciones principales, mientras que las diagonales inversas y diagonales 4 N - 2 forman las restricciones secundarias. Además, dado que cada una de primera y la última diagonal diagonales y inversa implica sólo un cuadrado en el tablero de ajedrez, estos pueden ser omitidos y por lo tanto se puede reducir el número de restricciones secundarias a 4 N - 6. La matriz para la N reinas problema, entonces tiene N 2 filas y 6 columnas N - 6, cada fila para una posible colocación de reina en cada cuadro del tablero de ajedrez, y cada columna para cada restricción.
No hay comentarios:
Publicar un comentario