Rompecabezas de 15 piezas

Johnson y Story (1879) utilizaron un argumento de paridad para demostrar que la mitad de las posiciones iniciales del rompecabezas n son imposibles de resolver, independientemente del número de movimientos. Esto se logra considerando una función binaria de la configuración de las fichas que permanece invariante ante cualquier movimiento válido, y luego utilizando esta función para dividir el espacio de todos los estados etiquetados posibles en dos clases de equivalencia mutuamente inaccesibles del mismo tamaño. Esto significa que la mitad de todas las posiciones son irresolubles, aunque no aporta información sobre la otra mitad.

El invariante es la paridad de la permutación de los 16 cuadrados más la paridad de la distancia en taxi (número de filas más número de columnas) del cuadrado vacío desde la esquina inferior derecha. Este es un invariante porque cada movimiento cambia tanto la paridad de la permutación como la paridad de la distancia en taxi. En particular, si el cuadrado vacío está en la esquina inferior derecha, el rompecabezas solo se puede resolver si la permutación de las piezas restantes es par.

Johnson y Story (1879) también demostraron que en tableros de tamaño m × n , donde m y n son mayores o iguales a 2, todas las permutaciones pares tienen solución. Esto se puede probar por inducción sobre m y n , comenzando con m = n = 2. Esto significa que existen exactamente dos clases de equivalencia de arreglos mutuamente accesibles, y que la paridad descrita es el único invariante no trivial, aunque existen descripciones equivalentes.

Archer (1999) dio otra demostración, basada en la definición de clases de equivalencia a través de una trayectoria hamiltoniana .

Wilson (1974) estudió la generalización del rompecabezas 15 a grafos finitos arbitrarios , siendo el problema original el caso de un grafo de cuadrícula de 4×4 . El problema tiene algunos casos degenerados donde la respuesta es trivial o una simple combinación de las respuestas al mismo problema en algunos subgrafos. Es decir, para caminos y polígonos , el rompecabezas no tiene libertad; si el grafo es desconectado , solo el componente conectado del vértice con el "espacio vacío" es relevante; y si hay un vértice de articulación , el problema se reduce al mismo rompecabezas en cada uno de los componentes biconectados de ese vértice. Excluyendo estos casos, Wilson demostró que, aparte de un grafo excepcional de 7 vértices, es posible obtener todas las permutaciones a menos que el grafo sea bipartito , en cuyo caso se pueden obtener exactamente las permutaciones pares. El grafo excepcional es un hexágono regular con una diagonal y un vértice en el centro añadidos; Solo se puede alcanzar 1/6 de sus permutaciones, lo que da un ejemplo de la incrustación exótica de S 5 _en S ₆ .

Para versiones más grandes del rompecabezas n , encontrar una solución es fácil. Pero el problema de encontrar la solución más corta es NP-difícil . También es NP-difícil aproximar la menor cantidad de deslizamientos dentro de una constante aditiva, pero hay una aproximación de factor constante de tiempo polinomial. ^{[ 2 ] [ 3 ]} Para el rompecabezas 15, las longitudes de las soluciones óptimas varían de 0 a 80 movimientos de una sola ficha (hay 17 configuraciones que requieren 80 movimientos) ^{[ 4 ] [ 5 ]} o 43 movimientos de múltiples fichas; ^{[ 6 ]} el rompecabezas 8 siempre se puede resolver en no más de 31 movimientos de una sola ficha o 24 movimientos de múltiples fichas (secuencia entera A087725 ). La métrica de múltiples fichas cuenta los movimientos subsiguientes de la ficha vacía en la misma dirección como uno. ^{[ 6 ]}

El número de posiciones posibles del rompecabezas de 24 piezas es ⁠ 25! / 2 ⁠ ≈7,76 × 10²⁴ , que es demasiado para calcular ^el número de Dios de manera factible usando métodos de fuerza bruta. En 2011, se establecieron límites inferiores de 152 movimientos de una sola ficha o 41 movimientos de varias fichas, así como límites superiores de 208 movimientos de una sola ficha o 109 movimientos de varias fichas. ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]} En 2016, el límite superior se mejoró a 205 movimientos de una sola ficha. ^{[ 11 ]}

Las transformaciones del rompecabezas 15 forman un grupoide (no un grupo, ya que no todos los movimientos se pueden componer); ^{[ 12 ] [ 13 ] [ 14 ]} este grupoide actúa sobre configuraciones.

Debido a que las combinaciones del rompecabezas 15 se pueden generar mediante ciclos de 3 , se puede demostrar que el rompecabezas 15 se puede representar mediante el grupo alternante.${\displaystyle A_{15}}$. ^{[ 15 ]} De hecho, cualquier${\displaystyle 2k-1}$Un rompecabezas deslizante con fichas cuadradas de igual tamaño se puede representar mediante${\displaystyle A_{2k-1}}$.

Desde 1891 hasta su muerte en 1911, Sam Loyd afirmó haber inventado el rompecabezas. Sin embargo, Loyd no tuvo ninguna relación con la invención ni con la popularidad inicial del mismo. Su primer artículo sobre el rompecabezas se publicó en 1886, y no fue hasta 1891 que afirmó por primera vez ser el inventor. ^{[ 16 ] [ 18 ]}

El interés posterior se vio impulsado por la oferta de Loyd de un premio de $1,000 ( equivalente a $35,833 en 2025 ) a cualquiera que pudiera proporcionar una solución para lograr una combinación particular especificada por Loyd, a saber, invertir el 14 y el 15, que Loyd llamó el rompecabezas 14-15 . ^{[ 1 ]} Esto es imposible, como lo habían demostrado más de una década antes Johnson y Story (1879) , porque requiere una transformación de una permutación par a una impar.