En 1880, el creador estadounidense de puzzles Sam Loyd anunció un premio de 1000 dólares a quien resolviera un 15-puzzle concreto: la disposición estándar 1‑a‑15 con el 14 y el 15 intercambiados. La fiebre por el puzzle ya barría América; el truco de Loyd echó gasolina. Miles lo intentaron. Nadie ganó.
Por una razón. El tablero de Loyd era demostrablemente irresoluble, y la demostración cabe en una página. Este artículo es esa página.
La afirmación
Exactamente la mitad de las 16!/2 ≈ 10 461 394 944 000 formas de disponer quince fichas y un hueco en un tablero 4×4 puede llevarse al objetivo estándar. La otra mitad no. El «14 y 15 intercambiados» de Loyd está en la mitad sin solución.
Se generaliza. En cada deslizante N×N, la mitad no tiene solución. El 3×3 8-puzzle tiene 9!/2 = 181 440 tableros resolubles de 362 880; los puzzles 24, 35 y demás siguen la misma regla.
Inversiones
La demostración necesita una definición. Lee las fichas en orden de lectura — izquierda a derecha por la fila 1, después la 2, la 3, la 4 — ignorando el hueco. Sale una secuencia de quince números.
Una inversión es un par (a, b) donde a aparece antes que b pero a > b. Cuenta cada par así sobre la secuencia. Ese conteo es el número de inversiones del tablero.
Ejemplo: el estado objetivo 1,2,3,…,15 tiene cero inversiones. El «14 y 15 intercambiados» tiene la secuencia 1,2,3,…,13,15,14, con exactamente una (par 15,14).
Lema clave: un deslizamiento cambia la paridad de forma controlada
¿Qué pasa con el número de inversiones en un movimiento legal?
-
Deslizamientos horizontales (una ficha izquierda/derecha): la ficha cambia su posición en la secuencia de lectura en una posición. Su orden relativo con cualquier otra ficha permanece igual — el movimiento horizontal no cambia la fila ni qué fichas la preceden o siguen en orden de filas. El conteo no cambia.
-
Deslizamientos verticales (arriba/abajo): la ficha salta tres otras fichas en la secuencia — las tres de la fila por la que pasa. Cada una se voltea de «después» a «antes» o viceversa, aportando ±1 al conteo. La suma de tres ±1 siempre es impar. El conteo cambia en un número impar.
Resumen: un deslizamiento horizontal preserva la paridad del conteo (par o impar). Uno vertical la voltea.
La fila del hueco también se voltea con los verticales
Sigue la fila del hueco, contando desde arriba. Un deslizamiento horizontal deja al hueco en la misma fila. Uno vertical lo mueve una fila — su paridad cambia.
Ahora dos cosas cambian juntas:
- Paridad de inversiones se voltea ⇔ deslizamiento vertical.
- Paridad de fila del hueco se voltea ⇔ deslizamiento vertical.
Su suma es por tanto invariante bajo cualquier movimiento legal. Hemos encontrado una cantidad conservada.
El teorema de paridad
Define la invariante:
P = (número de inversiones) + (número de fila del hueco, contado desde abajo, empezando en 1)
Esa es la cantidad conservada. En cada movimiento legal, P cambia en una cantidad par, así que su paridad (par o impar) nunca cambia.
El estado objetivo tiene cero inversiones y el hueco en la fila 1 desde abajo — así que P = 1 (impar). Cualquier tablero con P par es inalcanzable desde el objetivo, y viceversa.
Eso da un test de solubilidad limpio para el 15-puzzle:
- Lee las fichas en orden de filas, ignorando el hueco.
- Cuenta inversiones.
- Cuenta la fila del hueco desde abajo (1, 2, 3 o 4).
- Suma. Si es impar, el tablero tiene solución. Si es par, no.
El «14 y 15 intercambiados» de Loyd tiene 1 inversión y el hueco en la fila 1 desde abajo — suma 2, par, irresoluble.
Cómo es para otros tamaños
La regla N×N depende de si N es par o impar. La regla general:
- N impar (3×3, 5×5, …): un tablero es resoluble si y solo si el número de inversiones es par. La fila del hueco no importa, porque su paridad queda determinada por la del conteo por razones de simetría.
- N par (4×4, 6×6, …): un tablero es resoluble si y solo si (inversiones) + (fila del hueco desde abajo) es impar.
Para 3×3, el test es solo «¿número par de inversiones?». Más simple que el 4×4, memorizable en un minuto.
Consecuencia agradable
Como exactamente la mitad de las disposiciones tienen solución, una mezcla aleatoria más comprobación de paridad es más rápida que una mezcla aleatoria más intento de solución. Las apps que garantizan posiciones iniciales resolubles o bien:
- Pre-comprueban con el test de paridad y re-mezclan si falla.
- Generan caminando hacia atrás desde el objetivo, aplicando movimientos válidos al azar. Garantiza solubilidad por construcción y es lo que hacen casi todas las apps, la nuestra incluida.
Si alguna vez juegas a un deslizante y lo encuentras imposible, la app lo generó mal — no es culpa tuya, y no es un puzzle traído del universo.
La nota al pie sobre Sam Loyd
El premio de 1000 dólares de Loyd es uno de los chistes prácticos mejor documentados de la historia de los puzzles. El matemático que demostró la imposibilidad — de forma independiente — fue o bien William Johnson y William Story (1879, American Journal of Mathematics) o el propio Loyd, según a quién creas. Loyd era una figura célebremente autopromocional que reclamó varias invenciones que no eran suyas; el 15-puzzle lo inventó Noyes Chapman en 1874, seis años antes del premio.
Lo que Loyd realmente aportó fue el premio, la publicidad y la variante irresoluble — una contribución útil, aunque no la que anunciaba.