8 Puzzle

8 Puzzle, ¿Por qué el 8-puzzle tiene 9! / 2 = 181, 440 estados alcanzables?
Se realizó un cuestionamiento en clase, ¿Por qué el 8-puzzle tiene 9! / 2 = 181, 440 estados alcanzables? después deinvestigar un poco en la red descubrimos varias razones, la más adecuada y comprobable se refiere a la permutación de los estados y dado a que la mitad son inalcanzables justificándose con la imposibilidadde mover dos piezas del puzzle adyacentes. Se tienen 9 piezas, 8 piezas numeradas y una pieza vacía, en un cuadro dividido en 9 cuadros donde se colocan dichas piezas, por consiguiente el númerototal de combinaciones o estados es factorial del total de cuadros, 9!, que equivale a 362,880 estados, pero, es necesario dividir dichos estados resultantes en dos grupos, los alcanzables y los noalcanzables, donde los primeros son el conjunto de estados resultantes a partir de un estado inicial y un estado final solucionan el problema y por otra parte los que no satisfacen una solución alproblema.
Detección de puzzles que no se pueden resolver

Desde cualquier tablero inicial no siempre es posible alcanzar el estado meta. El programa debe detectar si un tablero se puede resolver o no. Elnúmero de tableros posibles en el 8-Puzzle es igual al número de permutaciones de 9 elementos, es decir, 9! = 362880. Se tiene que 8-Puzzle, tiene la propiedad de que está compuesto por 2 grafosdesconectados, cada uno conteniendo 9!/2 = 181440 estados. Por lo que se hace imperativo tener una forma eficiente de detectar si un estado se puede resolver o no.

Naturalmente, el número de diferentesordenaciones de 9 símbolos sin repetición son precisamente, todas sus permutaciones: 9! = 362,880. En otras palabras, en el problema del 8-puzle, que consiste en 9 constantes, el número de estadosposibles son 362.880. Sin embargo, resulta fácil observar que no todos ellos son alcanzables desde el estado final descrito anteriormente:

De una parte, resulta fácil observar que el número de...