Unstar es la versión espacial de un rompecabezas con casi 50 años de historia y una teoría matemática sorprendentemente bonita.

1. 1970s
   Merlin, de Parker Brothers, trae un juego con estas reglas en una cuadrícula de 3×3.
2. 1983
   XL-25, de Vulcan Electronics, lleva la idea a 5×5.
3. 1989
   Klaus Sutner publica en The Mathematical Intelligencer que, desde todas las luces encendidas, siempre se puede llegar a todas apagadas, en cualquier tamaño de cuadrícula.
4. 1995
   Tiger Electronics lanza Lights Out (5×5), creado por un equipo que incluye a Avi Olti y Gyora Benedek. Le siguen Lights Out 2000 (con varios colores), Lights Out Deluxe (6×6) y Lights Out Cube.
5. 1998
   Marlow Anderson y Todd Feil publican en Mathematics Magazine “Turning Lights Out with Linear Algebra”: no todo tablero de 5×5 tiene solución, y los que la tienen tienen exactamente cuatro.
6. 2013
   Rudolf Fleischer y Jiajin Yu publican un panorama completo del juego y sus variantes.
7. 2026
   Unstar lo convierte en un viaje de 2×2 a 10×10, de Mercurio a Plutón.

Numera las n² estrellas y escribe el tablero como una lista de ceros y unos: 1 si está encendida, 0 si no. Eso es un vector b en 𝔽₂^n², donde 𝔽₂ = {0, 1} es la aritmética “módulo 2”: 1 + 1 = 0.

Tocar la estrella i suma (módulo 2) un vector fijo a_i, con unos en i y sus vecinas. Que 1 + 1 = 0 es exactamente la regla “dos toques se cancelan”, y que la suma sea conmutativa es la regla “el orden no importa”.

Si x_i ∈ {0, 1} dice si tocas la estrella i, resolver el tablero es encontrar x con

Si M es la matriz de adyacencia de un camino de n puntos (unos justo arriba y abajo de la diagonal), la matriz del tablero de n×n es

El símbolo ⊗︎ es el producto de Kronecker: M ⊗︎ I pone una copia de I en cada lugar donde M tiene un 1. Es la forma corta de decir “aplica la regla de una fila a todas las columnas” (y viceversa), sin escribir la matriz de n²×n² completa.

Es simétrica (si yo te cambio, tú me cambias) y eso va a importar. Para el 2×2, con las estrellas numeradas 1 2 / 3 4:

Primero hay que aclarar el tamaño. El tablero de 2×2 tiene 4 estrellas, y la pregunta es “¿toco esta estrella o no?” para cada una. Así que hay 4 incógnitas, x₁ a x₄, numeradas 1 2 / 3 4. Por eso la matriz es de 4×4 y no de 2×2: un 3×3 da 9 incógnitas y Plutón (10×10) da 100.

Luego se escribe una ecuación por estrella. La estrella 1 cambia si tocas la 1, la 2 o la 3. Al final tiene que haber cambiado un número impar de veces si empezó encendida y un número par si empezó apagada. En módulo 2:

Los números de la izquierda forman la matriz A: cada fila es una estrella y cada columna es un toque posible. A es la misma para cualquier tablero de 2×2, porque solo depende de quién es vecino de quién. Lo que cambia de un nivel a otro es el lado derecho b. La matriz aumentada [A | b] es solo A con la columna del tablero pegada a la derecha. Se pega para que, al sumar una fila con otra, el resultado cambie igual, como cuando sumas dos ecuaciones completas.

Ahora sí, un ejemplo: las estrellas 1 y 4 encendidas, b = (1, 0, 0, 1). En 𝔽₂ la única operación que hace falta es sumar una fila a otra (restar es lo mismo que sumar, y no hay nada que dividir):

Al final la izquierda es la identidad y la columna de la derecha es la solución: x = (1, 0, 0, 1). Hay que tocar las estrellas 1 y 4. Resolver el sistema te dice directamente qué estrellas tocar; en Plutón serían 100 ecuaciones con 100 incógnitas, y el resultado sería la lista exacta de estrellas. Compruébalo:

La regla para escribir la ecuación de cualquier estrella, en cualquier tamaño, es siempre la misma:

Pruébalo aquí. Marca las estrellas encendidas y la página escribe las ecuaciones y la matriz aumentada. Pasa el mouse por una estrella para ver qué incógnitas entran en su ecuación. Luego dale a “Resolver con Gauss” y avanza paso a paso: al final te marca qué estrellas tocar. En 4×4 vas a ver columnas sin pivote, y a veces una fila 0 = 1, que es la forma en que el álgebra te dice que ese tablero no tiene solución.

En 3×3, A es invertible, así que x = A⁻¹b. Cada columna de A⁻¹ tiene un significado muy concreto: qué tocar para cambiar una sola estrella y dejar todo lo demás igual. Son nueve recetas:

Para resolver cualquier 3×3: junta las recetas de cada estrella encendida y toca las estrellas que salgan un número impar de veces. Eso es literalmente multiplicar A⁻¹ por b.

Reto: resuelve este tablero solo con las recetas, sin barrer. Tiene 5 estrellas encendidas.

Si A no es invertible, hay vectores q ≠ 0 con A q = 0: conjuntos de toques que no cambian nada. Los llamamos patrones quietos. Forman el núcleo ker A.

Como A es simétrica, la imagen de A es exactamente el complemento ortogonal de su núcleo:

La mitad fácil: si b = A x, entonces b · q = x · A q = 0. La otra mitad sale de contar dimensiones: dim im A = n² − dim ker A = dim (ker A)^⊥.

En 5×5 el núcleo tiene dimensión 2, así que hay dos condiciones independientes y solo 1 de cada 4 cielos al azar se puede apagar. Unstar nunca te da uno de los otros tres, porque cada nivel se construye tocando desde el cielo apagado.

Si un tablero tiene solución x, todas sus soluciones son x + q con q quieto. Si d(n) = dim ker A, hay 2^d soluciones y una fracción 1/2^d de los cielos tiene solución.

¿De dónde salen esos números tan irregulares? Los valores propios de A = I + M⊗︎I + I⊗︎M son 1 + λ + μ, con λ y μ valores propios de M. En característica 2, 1 + λ + μ = 0 significa μ = λ + 1. El polinomio característico de M sobre 𝔽₂ es un polinomio de Chebyshev:

y la dimensión del núcleo es

Así que Plutón (10×10) tiene solución única, pero 19×19 tendría 65,536 soluciones por tablero.

Barrer no es un truco aparte: es eliminación de Gauss hecha con los dedos. Una vez que decides la fila de arriba t ∈ 𝔽₂ⁿ, el barrido decide todo lo demás. Por eso el problema de n² incógnitas se reduce a n (en Plutón, de 100 ecuaciones a 10): lo que queda abajo depende linealmente de t,

La tabla del telescopio es simplemente C⁻¹ (o una preimagen cuando C no es invertible), y la “tabla por luz” de los tableros grandes son sus columnas, que se pueden sumar porque todo es lineal. Además dim ker C = dim ker A, así que:

• En 4×4, C = 0. Cualquier fila de arriba funciona, y por eso en la Tierra barrer siempre apaga todo.
• En 5×5, C tiene rango 3: solo hay 8 restos posibles (7 sin contar el vacío), las 7 filas de la tabla.
• En 9×9, C tiene rango 1: un solo resto posible.

Encontrar una solución es fácil. Encontrar la que usa menos toques es otro problema: entre las 2^d soluciones x + q, hay que elegir la de menos unos. En general, buscar el vector de peso mínimo en una clase lateral es un problema difícil (es el problema de decodificación de códigos lineales), pero aquí d es chico: Unstar prueba las 2^d combinaciones de una base del núcleo (hasta 256 en Neptuno) y se queda con la más corta. Ese es el número “Mínimo” que ves en pantalla.

Cuando d = 0 no hay que elegir: la única solución es la mínima. Por eso en la guía avanzada el truco de “barrer, deshacer, tocar arriba y barrer una vez” da oro garantizado en esos tamaños.

El tablero con todas las estrellas encendidas es b = (1, 1, …, 1). Sutner demostró que siempre tiene solución. Con la sección 6 sale en dos líneas: si q es quieto, q · A q = 0. Como A es simétrica, los términos fuera de la diagonal aparecen por pares y se cancelan, y como la diagonal es de unos queda q · q, que es el número de unos de q. Entonces todo patrón quieto tiene un número par de estrellas y (1, …, 1) · q = 0.

El mínimo para 5×5 es de 15 toques. Inténtalo:

Todo lo anterior se generaliza, y cada generalización sería un modo de juego distinto:

• Más estados. Si cada estrella tiene k colores y un toque avanza un color, el juego vive en ℤ_k en vez de 𝔽₂ (Lights Out 2000 usaba varios colores). Con k primo sigue siendo álgebra lineal sobre un campo, pero tocar dos veces ya no cancela y el mínimo cambia por completo.
• Otras vecindades. Cambiar en X (diagonales), cambiar solo a las vecinas y no a la propia estrella, o el salto del caballo de ajedrez. Cada una cambia la matriz y con ella qué tamaños tienen solución única.
• Otras formas. Tableros hexagonales, toros (lo que sale por un lado entra por el otro), cubos como Lights Out Cube, o cualquier grafo. El argumento de la sección 10 funciona igual en todos: desde todo encendido siempre se puede apagar.
• Un nivel de álgebra lineal. Un tablero donde el juego te muestre la matriz y tú resuelvas el sistema en vez de tocar al tanteo.

¿Te gustaría jugar alguno de estos en Unstar? Escríbenos a periastrostudio@gmail.com.

1. K. Sutner, “Linear cellular automata and the Garden-of-Eden”, The Mathematical Intelligencer 11 (1989).
2. M. Anderson y T. Feil, “Turning Lights Out with Linear Algebra”, Mathematics Magazine 71(4) (1998).
3. R. Fleischer y J. Yu, “A Survey of the Game ‘Lights Out!’”, Lecture Notes in Computer Science 8066 (2013).
4. Lights Out Puzzle, Wolfram MathWorld.
5. Lights Out (game), Wikipedia.
6. OEIS A075462 (número de soluciones) y A075464 (mínimo desde todo encendido).