Cada movimiento en el 8 rompecabezas (o su hermano mayor el 15 rompecabezas) intercambia la posición de dos mosaicos: el mosaico “vacío” y uno de sus vecinos. Si consideramos el rompecabezas como una permutación del estado de la solución, esto significa que cada movimiento cambia entre una permutación impar (una creada por un número impar de transposiciones) y una permutación par.
Cada movimiento en el rompecabezas 8 también cambia la “distancia de la cuadra de la ciudad” (o “distancia del taxi”) entre el cuadrado vacío y la esquina superior derecha en uno. (Podríamos usar cualquier punto de referencia, no importa). Esta distancia es solo la suma del número de movimientos “hacia la izquierda” y el número de movimientos “hacia arriba” para llegar a la posición superior derecha. Entonces, cada movimiento cambia la paridad de la distancia. Si el espacio en blanco era un número impar de movimientos de distancia antes del movimiento, será un número par de movimientos de distancia después del movimiento.
La combinación de estos dos cambios en la paridad significa que la mitad de las posiciones son inalcanzables desde cualquier posición inicial.
- ¿Qué es un promedio móvil y, algorítmicamente, cómo se calcula dicho conjunto?
- ¿Cómo explicarías un 'arreglo' a un principiante en programación?
- ¿Por qué no se utilizan algoritmos genéticos?
- ¿Cuál es el algoritmo detrás de la creación de una nueva fuente que solo muestra publicaciones de tus seguidores?
- ¿Cuál es el algoritmo más ineficiente para los estándares actuales que se usa ampliamente en la industria?
Supongamos que comenzamos con el rompecabezas resuelto: la identidad es una permutación uniforme, y las distancias desde la izquierda inferior a la superior derecha en el rompecabezas 8 es 4, incluso par. El primer movimiento que hacemos hace que la permutación sea extraña y la distancia impar. El segundo movimiento nos lleva de vuelta a una permutación pareja y una distancia pareja. Cada movimiento cambia ambas paridades; Es imposible llevar a los dos a diferentes estados.
Eso significa que cualquier posición que requiera una permutación impar y una distancia par, o una permutación par y una distancia impar, no es accesible desde la solución.
Entonces solo tenemos que mostrar que hay tantas posiciones con (impar [permutación], par [distancia]) y (par, impar) como hay posiciones con (impar, impar) e (par, par). Pero esto es bastante simple. Toma cualquier posición alcanzable. En la fila con el cuadrado vacío debe haber dos cuadrados no vacíos. Si los transponemos, eso cambia la paridad de la posición, pero no la paridad de la distancia del cuadrado vacío. Esto produce una biyección entre (impar, par) e (par, par) y una biyección entre (par, impar) y (impar, impar) posiciones, por lo que deben ser de igual cardinalidad.
Si el rompecabezas te permitiera intercambiar dos fichas arbitrarias, entonces cualquier posición sería accesible. Pero debido a que el rompecabezas solo le permite intercambiar el mosaico vacío con uno de sus vecinos, esto impone una restricción adicional cuya paridad significa que la mitad de las posiciones son inalcanzables. Para decirlo de otra manera, no podemos intercambiar solo dos fichas. Tenemos que intercambiar al menos dos fichas y mover el espacio vacío, o hacer al menos dos intercambios para restaurar la posición del espacio vacío.
