algorithm - inteligencia - heuristica manhattan 8 puzzle java

¿Cuántos estados posibles tiene el 8-puzzle?

Question

El clásico 8-puzzle pertenece a la familia de los bloques deslizantes. Mi libro (Inteligencia artificial Un enfoque moderno de Stuart Russell y Peter Norwig) dice que el 8-puzzle tiene 9! / 2 estados posibles. Pero ¿POR QUÉ el / 2 ? ¿Cómo se consigue esto?

Answer 1

9! es el número total de configuraciones posibles del rompecabezas, mientras que 9!/2 es el número total de configuraciones solubles . Por ejemplo, esta configuración no tiene una solución:

1 2 3
4 5 6
8 7

Lea más sobre la solvencia de ciertas configuraciones del n-puzzle en este article Wikipedia, o como lo señaló @dasblinkenlight en esta explicación de MathWorld.

Una forma posible de descubrir que 9!/2 es el número de configuraciones solubles es partir de un rompecabezas resuelto y generar a partir de él todos los posibles movimientos válidos y no repetitivos.