Si alguna vez has pasado treinta minutos con un 15-puzzle que simplemente no termina — cada movimiento acaba con dos fichas intercambiadas al final —, hay una posibilidad de que el puzzle sea matemáticamente irresoluble. Exactamente la mitad de las disposiciones lo son. Una app mal escrita puede generar uno por accidente.
Este artículo es la comprobación práctica. La justificación completa vive en el teorema de paridad; aquí va sencillo.
La comprobación de 30 segundos
Mira las fichas en orden de lectura — izquierda a derecha por filas, de arriba abajo — ignorando el hueco.
Para cada par de fichas, cuenta cuántas veces un número mayor aparece antes que uno menor. Ese conteo es el número de inversiones.
Después, fíjate en qué fila está el hueco, contando desde abajo (la fila inferior es 1, la siguiente arriba es 2, después 3 y 4 arriba).
Suma el número de inversiones y la fila desde abajo. Si el resultado es impar, el puzzle tiene solución. Si par, no.
Eso es todo. Es toda la comprobación.
Ejemplo trabajado
Imagina que tu tablero es:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Orden de lectura: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Cuenta inversiones. Necesitamos cada par donde el mayor va antes que el menor. Recorriendo: el 15 aparece antes que el 14, y esa es la única. Así que inversiones = 1.
El hueco está en la fila inferior → fila 1 desde abajo.
Suma: 1 + 1 = 2. Par. Este tablero es irresoluble.
Este es, de hecho, el puzzle del premio de Sam Loyd de 1880. El hombre ofreció 1000 dólares a quien lo resolviera. Era irresoluble; conservó su dinero.
Otro ejemplo
Tablero:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Orden de lectura: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Cuenta inversiones:
- 5 antes de 1 → 1 inversión (5 > 1, y el 5 va primero)
- 5 antes de 3 → 1
- 5 antes de 4 → 1
- 5 antes de 2 → 1
- 3 antes de 2 → 1
- 4 antes de 2 → 1
Inversiones totales: 6.
Hueco en la fila inferior → fila 1.
Suma: 6 + 1 = 7. Impar. Tiene solución.
Por qué funciona (en corto)
Un movimiento legal o mueve una ficha horizontalmente (sin cambiar inversiones ni fila del hueco) o verticalmente (cambia inversiones en un número impar, cambia la fila del hueco en 1).
En ambos casos, la suma inversiones + fila del hueco mantiene su paridad par-o-impar inicial. Esa suma es invariante — una propiedad que los movimientos legales no cambian.
El objetivo (1‑2‑3‑...‑15 con hueco abajo-derecha) tiene 0 inversiones y hueco en fila 1 desde abajo. Suma: 1, impar. Así, todo puzzle resoluble tiene suma impar. Todo puzzle con suma par no puede llegar al objetivo.
Para la demostración completa con todos los casos, ver la página del teorema.
¿Y los 8-puzzles (3×3)?
Para 3×3 la comprobación es más simple:
- Cuenta inversiones en orden de lectura.
- Si par, resoluble.
- Si impar, irresoluble.
No hace falta rastrear la fila del hueco en 3×3 — la simetría hace redundante esa dependencia.
(Para 5×5 — misma regla que 3×3. Para 6×6 — misma regla que 4×4. La regla es «la fila del hueco importa cuando N es par».)
Qué hacer si tu app genera puzzles irresolubles
No debería pasar. Una app bien escrita usa uno de dos métodos:
Generar caminando hacia atrás desde el objetivo. Empezar desde el estado objetivo, aplicar movimientos válidos al azar, y el resultado es la posición inicial. Toda posición así generada tiene solución por construcción.
Generar aleatorio, después comprobar paridad. Mezcla las fichas uniformemente al azar; calcula la paridad; si es par, intercambia dos fichas cualesquiera para corregir. La posición resultante tiene solución garantizada.
Si encuentras un puzzle irresoluble en una app, esa app está rota. Informa del bug, cambia de app. Slide Puzzle usa el método de caminar hacia atrás y no puede producir posiciones iniciales sin solución.
Qué hacer si sospechas de tu puzzle físico
Dos cosas:
- Haz la comprobación. Inversiones más fila del hueco. Si es par, las piezas físicas se montaron mal. Saca una ficha, intercámbiala con una vecina, y el puzzle vuelve a ser resoluble.
- Si tras un intercambio el puzzle te sigue resistiendo — la resistencia es tu estrategia, no el puzzle.
La comprobación lleva treinta segundos. Hacerla antes de hundir otra hora en un tablero atascado es un uso razonable de esos segundos.