Hispanopedia WikiLos rompecabezas de mesa con álgebra de variables binarias piden a los jugadores que localicen los objetos ocultos a partir de un conjunto de celdas de pistas y sus vecinas marcadas como variables (incógnitas). Una variable con valor 1 corresponde a una celda con un objeto. Por el contrario, una variable con valor 0 corresponde a una celda vacía, sin objeto oculto.
Descripción general
Estos rompecabezas se basan en álgebra con variables binarias que toman pares de valores, por ejemplo, (no, sí), (falso, verdadero), (no existe, existe), ( 0 , 1 ). Invitan al jugador a establecer rápidamente ecuaciones e inecuaciones para la solución. La partición puede utilizarse para reducir la complejidad del problema. Además, si el rompecabezas está diseñado de tal manera que solo existe una solución única , este hecho puede utilizarse para eliminar algunas variables sin necesidad de cálculos.
El problema puede modelarse como programación lineal entera binaria , que es un caso especial de programación lineal entera. [ 1 ]
Historia
El Buscaminas , junto con sus variantes , es el ejemplo más notable de este tipo de rompecabezas.
Álgebra con variables binarias
Debajo de las letras en las expresiones matemáticas se utilizan como variables, cada una de las cuales solo puede tomar el valor 0 o 1. A continuación se muestra un ejemplo sencillo de una ecuación con variables binarias:
- a + b = 0
Aquí hay dos variables, a y b, pero una sola ecuación. La solución está limitada por el hecho de que a y b solo pueden tomar los valores 0 o 1. Solo hay una solución: a = 0 y b = 0. A continuación se muestra otro ejemplo sencillo:
- a + b = 2
La solución es sencilla: a y b deben ser 1 para que a + b sea igual a 2 .
Otro caso interesante se muestra a continuación:
- a + b + c = 2
- a + b ≤ 1
Aquí, la primera afirmación es una ecuación y la segunda es una desigualdad que indica los tres casos posibles:
- a = 1 y b = 0 ,
- a = 0 y b = 1 , y
- a = 0 y b = 0 ,
El último caso provoca una contradicción en c al forzar c = 2 , lo cual no es posible. Por lo tanto, uno de los dos casos es correcto. Esto lleva a la conclusión de que c debe ser 1 .
La modificación de una ecuación grande a una forma más pequeña no es difícil. Sin embargo, un sistema de ecuaciones con variables binarias no siempre se puede resolver aplicando álgebra lineal . El siguiente es un ejemplo de cómo aplicar la resta de dos ecuaciones:
- a + b + c + d = 3
- c + d = 1
La primera afirmación tiene cuatro variables, mientras que la segunda solo tiene dos. Esto último significa que la suma de c y d es 1. Usando este hecho en la primera afirmación, las ecuaciones anteriores se pueden reducir a:
- a + b = 2
- c + d = 1
El álgebra en una pizarra
Un juego basado en álgebra con variables binarias puede visualizarse de diversas maneras. Una representación genérica consiste en representar el lado derecho de una ecuación como una pista en una celda (celda de pista) y las celdas vecinas de una celda de pista como variables. En la Figura 1 se muestra un caso sencillo. Se puede asumir que las celdas vecinas son las celdas arriba/abajo, izquierda/derecha y las de las esquinas que comparten un borde o una esquina. Las celdas blancas pueden contener un objeto oculto o estar vacías. En otras palabras, son las variables binarias. Se ubican en el lado izquierdo de las ecuaciones. Cada celda de pista, una celda con fondo azul en la Figura 1, contiene un número positivo que corresponde al número de sus vecinas que tienen objetos ocultos. El número total de objetos en el tablero puede proporcionarse como una pista adicional. El mismo tablero con las variables marcadas se muestra en la Figura 2.
La reducción a un conjunto de ecuaciones con variables binarias
La ecuación principal se escribe utilizando el número total de objetos ocultos dado. De la primera figura, esto corresponde a la siguiente ecuación.
- a + b + c + d + e + f + g + h + i + j + k + m = 3
Las demás ecuaciones se componen una a una para cada celda de pista:
- a + b + c + e + f + h + i + j = 1
- f + g + j + m = 1
- h + i + j + k = 2
- i + j + m = 2
Aunque existen varias formas de resolver las ecuaciones anteriores, se puede aplicar el siguiente método explícito:
- Se sabe por el conjunto de ecuaciones que i + j + m = 2. Sin embargo, dado que j y m son vecinos de una celda con número 1 , se cumple lo siguiente: j + m ≤ 1. Esto significa que la variable i debe ser 1 .
- Dado que i = 1 y la variable i es vecina de la celda de pista con el número 1 , las variables a , b , c , e , f , h y j deben ser cero. El mismo resultado se puede obtener reemplazando i = 1 en la segunda ecuación de la siguiente manera: a + b + c + e + f + h + j = 0. Esto es equivalente a a = 0 , b = 0 , c = 0 , e = 0 , f = 0 , h = 0 , j = 0 .
- La Figura 3 se obtiene después de los Pasos 1 y 2. Las celdas sombreadas con '–' son las variables con valor 0. La celda con el símbolo Δ corresponde a la variable con valor 1. La variable k es el único vecino de la celda de pista más a la izquierda con valor 2. Esta celda de pista tiene un vecino con un objeto y solo una celda restante con la variable k . Por lo tanto, k debe ser 1 .
- De manera similar, la variable m también debe ser 1 porque es la única variable vecina restante a la celda de pista más a la derecha con valor 2 .
- Dado que k = 1 , m = 1 e i = 1 , completamos el marcado de tres objetos ocultos, por lo tanto d = 0 y g = 0. La solución final se muestra en la Figura 4.
Uso de la singularidad
En el ejemplo anterior (Figura 2), las variables a , b , c y e son vecinas de la celda de pista 1 y no son vecinas de ninguna otra celda. Es obvio que las siguientes son posibles soluciones:
- a = 1 , b = 0 , c = 0 , e = 0
- a = 0 , b = 1 , c = 0 , e = 0
- a = 0 , b = 0 , c = 1 , e = 0
- a = 0 , b = 0 , c = 0 , e = 1
Sin embargo, si el rompecabezas está diseñado de manera que tenga una única solución, podemos establecer que todas estas variables a , b , c y e deben ser 0. De lo contrario, habrá más de una solución.
Uso de particionamiento
Algunas configuraciones de rompecabezas pueden permitir al jugador usar particiones [ 2 ] para reducir la complejidad. Un ejemplo se muestra en la Figura 5. Cada partición corresponde a una cantidad de objetos ocultos. La suma de los objetos ocultos en las particiones debe ser igual a la cantidad total de objetos ocultos en el tablero. Una forma posible de determinar una partición es elegir las celdas de pista principal que no tienen vecinos comunes. Las celdas fuera de las zonas rojas transparentes en la Figura 5 deben estar vacías. En otras palabras, no hay objetos ocultos en las celdas completamente blancas. Dado que debe haber un objeto oculto dentro de la zona de partición superior, la tercera fila desde arriba no debe contener un objeto oculto. Esto lleva a que las dos celdas variables en la fila inferior alrededor de la celda de pista deben tener objetos ocultos. El resto de la solución es sencillo.
Uso del método de ensayo y error
En algunos casos, el jugador puede establecer una celda variable en 1 y comprobar si se produce alguna inconsistencia. El ejemplo de la Figura 6 muestra una comprobación de inconsistencia. La celda marcada con un objeto oculto Δ está bajo prueba. Su marcado lleva a establecer todas las variables (celdas sombreadas) en 0. Esto sigue a la inconsistencia. La celda de pista marcada en rojo con valor 1 no tiene ningún vecino restante que pueda contener un objeto oculto. Por lo tanto, la celda bajo prueba no debe contener un objeto oculto. En forma algebraica tenemos dos ecuaciones:
- a + b + c + d = 1
- a + b + c + d + e + f + g = 1
Aquí , a , b , c y d corresponden a las cuatro celdas sombreadas superiores de la Figura 6. La celda con Δ está representada por la variable f , y las otras dos celdas sombreadas están marcadas como e y g . Si establecemos f = 1 , entonces a = 0 , b = 0 , c = 0 , d = 0 , e = 0 , g = 0. La primera ecuación anterior tendrá el lado izquierdo igual a 0, mientras que el lado derecho tiene 1. Una contradicción.
En algunos rompecabezas, puede ser necesario aplicar el método de prueba y error en más de un paso para llegar a una conclusión. Esto equivale al algoritmo de búsqueda binaria [ 3 ] para eliminar posibles rutas que conduzcan a inconsistencias.
Complejidad
Debido a que se trata de variables binarias, el sistema de ecuaciones para la solución no posee linealidad. En otras palabras, el rango de la matriz de ecuaciones no siempre refleja la complejidad adecuada.
La complejidad de este tipo de rompecabezas se puede ajustar de varias maneras. Uno de los métodos más sencillos consiste en establecer una proporción entre el número de celdas de pista y el número total de celdas del tablero. Sin embargo, esto puede resultar en un rango de complejidad muy variable para una proporción fija. Otro método consiste en reducir las celdas de pista paso a paso, basándose en estrategias de resolución de problemas . Las estrategias complejas pueden activarse para niveles de complejidad altos, como restar una ecuación con otra o una mayor profundidad en los pasos de prueba y error. A medida que aumenta el tamaño del tablero, aumenta el rango de casos problemáticos. La proporción entre el número de objetos ocultos y el número total de celdas también afecta la complejidad del rompecabezas.
Notas
Referencias
- Paul Halmos , Teoría ingenua de conjuntos . Princeton, NJ: D. Van Nostrand Company, 1960. Reimpreso por Springer-Verlag, Nueva York, 1974. ISBN 0-387-90092-6(Edición de Springer-Verlag).
- Alexander Schrijver , Teoría de la programación lineal y entera . John Wiley & Sons, 1986. Reimpreso en 1999. ISBN 0-471-98232-6.
- Adam Drozdek, Estructuras de datos y algoritmos en C++ , Brooks/Cole, segunda edición, 2000. ISBN 0-534-37597-9.
- Rompecabezas
- Álgebra
- Variables (matemáticas)
- Ecuaciones
