Puzzle de bloques deslizantes

Question

Consideremos un "juego" jugado en un subconjunto $S$ de un $n^2$ cuadrado de la siguiente manera. Hay 3 tipos de piezas, cada una ocupa una casilla, 1 verde, otras rojas y el resto son azules, un movimiento consiste en barajar la pieza verde con cualquiera de sus 4 piezas adyacentes (si están dentro de $S$ ). $S$ se compone de casillas, casillas que no están en $S$ son estáticos, $S$ puede ser cualquier subconjunto del $n^2$ cuadrado.

Si dos configuraciones de tablero son alcanzables entre sí, ¿es posible obtener un límite superior en el número de movimientos necesarios, dado sólo el tamaño del tablero $n$ ¿es polinómico en $n$ ?

Answer 1

Pista: considera las configuraciones con un cuadrado rojo y el resto (excepto el verde) azul. ¿Puedes demostrar que cualquiera de ellas puede convertirse en cualquier otra en un número polinómico de movimientos? Si el número de casillas rojas y azules difiere, no puedes arreglarlo. Si no lo son, numere los cuadrados rojos y azules en las dos configuraciones. Fija la esquina superior izquierda, luego la casilla de al lado, y así sucesivamente. Hay menos de $n^2$ cuadrados para arreglar. Todavía tienes que demostrar que no vas a molestar a los que ya has resuelto, pero eso no debería ser difícil a excepción de la última casilla de la fila.