¿Qué es un buen método para demostrar la solvencia de este tipo de puzzle sin uso de fuerza bruta?

Question

Me topé por casualidad con este rompecabezas en esta pregunta sobre el Anime Y el Manga sitio, y, como el OP, trató de resolverlo sin ningún éxito. Aquí es una representación del rompecabezas: los bloques sólo puede ser movido hacia adelante o hacia atrás a lo largo de sus lados más cortos, y debemos conseguir que el bloque marcado con una X negra a la salida.

Luego trató de demostrar que el rompecabezas no era solucionable mediante la siguiente estructura:

1. Argumentan que en algún momento el bloque se debe mover a la salida va a ser exactamente un espacio lejos de ella, y que por otra parte, tan solo necesitaremos para mover el resto de los bloques en la mayoría de los una vez para eliminar cualquier obstrucción a la salida.

2. El uso de la prueba por contradicción y el diseño de los rompecabezas para argumentar que ninguna de las configuraciones posibles para que el bloque está en el espacio en el que se especifique en realidad, en la mayoría de un solo movimiento que lejos de hacer la salida.

Me he topado con un muro de ladrillo con esto: hay cuatro casos posibles a considerar (basado en la colocación de (IV)), y aunque fácilmente podría aplicar (2) a dos de ellos, yo no tenía casi tanto éxito con las otras dos.

Me preguntaba si simplemente debería haber elegido una posición diferente a su trabajo, pero se me ocurrió que menos he tenido la gran suerte de intuición, sería difícil argumentar de otra cosa que de la penúltima colocación de los bloques. (Naturalmente, también se me ocurrió que yo podría, probablemente, sólo comprobar solvencia por escrito un programa de ordenador para comprobar que todas las configuraciones posibles de este rompecabezas, pero mis conocimientos de programación son inciertos, y me encontré con una "fuerza bruta" método demasiado uninsightful.) Por otra parte, la prueba de-estrategia sólo habría funcionado si el rompecabezas, de hecho, fueron irresoluble.

Supongo que no es necesariamente muy intuitiva generalización de encontrar la solvencia de dichos puzzles, pero por lo menos: ¿cuál sería una buena estrategia para que yo lo use para determinar si es o no este rompecabezas se puede resolver, sin demasiada fuerza bruta?

Answer 1

Es esta una instancia de la Hora punta? $\:$ Si sí, entonces:

No hay probablemente ninguna manera general para comprobar la solvencia de este
tipo de rompecabezas en mucho menos tiempo que el de la fuerza bruta tomaría.

No es una forma general para resolver resolver puzzles de este tipo (y descubrir
no solvencia cuando ese es el caso) con una cantidad de espacio que corresponde a alguna
constante de veces la cantidad de espacio necesario para representar una configuración del rompecabezas.
(Nota: $\:$ El algoritmo acabo vinculados a es muy poco práctico.)


Hay un estudio aleatorizado algoritmo con un tiempo-espacio de equilibrio para este tipo de rompecabezas
que seguramente tiene una alta probabilidad de reconocer resolver puzzles como solucionable y
nunca incorrectamente afirman que sin solución de rompecabezas es solucionable, aunque no
será una pequeña probabilidad de que al no reconocer una solución de rompecabezas como solucionable.
No sé si es o no, que puede convertirse en la solución de solución de puzzles de este tipo.

Hay una menos eficiente
el tiempo-espacio de intercambio (determinista) comprobación de la solvencia de este tipo de rompecabezas
y resolver resolver puzzles de este tipo (aunque el papel que acaba de vincular a
no hacer la afirmación de que corresponde a la "solución de resolver rompecabezas").
En uno de los extremos de la disyuntiva, de que este documento algoritmo reduce a la fuerza bruta.

Answer 2

Esta encuesta listas de este tipo de rompecabezas como PSPACE-completo, una clase que es al menos tan difícil como la clase de tipo NP-completo los problemas (y tal vez aún más difícil, pero no lo sabemos).

Esto significa que incluso un pequeño aumento en el puzzle tamaño podría causar un tremendo aumento en la dificultad, de tal forma que incluso los equipos no será capaz de resolver "razonable" de tiempo. No me he enterado de cualquiera de los métodos de demostración de solvencia de unsolvability en el caso general, que no se asemejan a un ataque de fuerza bruta enfoque. Quizás tales métodos de las subclases de este tipo de problemas (por ejemplo, cuando la partida de configuración está construido con algunos de los métodos conocidos), pero que es el mejor que se puede esperar menos que romper el resto del mundo.

De todos modos, esta instancia es solucionable, los siguientes consejos. (Por cierto, no es pedir en las matemáticas.SE alguna manera de comprobar si el puzzle es solucionable?)

Mover 8 a la izquierda:

6u 57r 1d 2l 36u 3d, 4r 2r 1u 5l 10u 5r 1d 2l 8l 39u

Mueva 6:

39d 2r 1u 5l 10d 5r 1d 2l 3u 4l 3d, 2r 1u 57l 6d

Mover 10:

57r 1d 2l 3u 3d, 4r 2r 1u 5l 10u

Espero que esto ayude a $\ddot\smile$