15 rompecabezas
El rompecabezas de 15 (también llamado Gem Puzzle , Boss Puzzle , Game of Fifteen , Mystic Square y muchos otros) es un rompecabezas deslizante que tiene 15 fichas cuadradas numeradas del 1 al 15 en un marco de 4 fichas de alto y 4 de ancho, dejando una desocupada. posición del azulejo. Los mosaicos en la misma fila o columna de la posición abierta se pueden mover deslizándolos horizontal o verticalmente, respectivamente. El objetivo del rompecabezas es colocar las fichas en orden numérico.
Nombrado por la cantidad de mosaicos en el marco, el rompecabezas de 15 también puede llamarse rompecabezas de 16, aludiendo a su capacidad total de mosaicos. Se utilizan nombres similares para variantes de diferentes tamaños del rompecabezas de 15, como el rompecabezas de 8 que tiene 8 fichas en un marco de 3 × 3.
El rompecabezas n es un problema clásico para modelar algoritmos que involucran heurística . Las heurísticas comúnmente utilizadas para este problema incluyen contar el número de baldosas mal colocadas y encontrar la suma de las distancias de taxi entre cada bloque y su posición en la configuración de la meta. [1] Tenga en cuenta que ambos son admisibles , es decir, nunca sobrestiman el número de movimientos restantes, lo que garantiza la optimización de ciertos algoritmos de búsqueda como A * . [1]
Johnson & Story (1879) utilizaron un argumento de paridad para mostrar que la mitad de las posiciones iniciales del n rompecabezas son imposibles de resolver, sin importar cuántos movimientos se hagan. Esto se hace considerando una función de la configuración de mosaico que es invariante bajo cualquier movimiento válido, y luego usándola para dividir el espacio de todos los posibles estados etiquetados en dos clases de equivalencia de estados alcanzables e inalcanzables.
El invariante es la paridad de la permutación de los 16 cuadrados más la paridad de la distancia del taxi (número de filas más número de columnas) del cuadrado vacío de la esquina inferior derecha. Esto es invariante porque cada movimiento cambia tanto la paridad de la permutación como la paridad de la distancia del taxi. En particular, si el cuadrado vacío está en la esquina inferior derecha, entonces el rompecabezas se puede resolver si y solo si la permutación de las piezas restantes es pareja.
Johnson & Story (1879) también demostraron que el recíproco sostiene en las juntas de tamaño m × n proporcionado m y n son ambos al menos 2: todas las permutaciones incluso son resolubles. Esto es sencillo pero un poco desordenado para demostrar por inducción sobre m y n empezando con m = n = 2. Archer (1999) dio otra prueba, basada en la definición de clases de equivalencia a través de un camino hamiltoniano .
