Acerca de Reto Pixelea

El Reto Pixelea

Este rompecabezas es un caso especial del juego Pixelea, en el que la única diferencia es que la distribución inicial es siempre la misma. Lo he añadido porque permite comparar soluciones: todos los usuarios resuelven el mismo rompecabezas así que se puede añadir un ránking (o sea, ¡más divertido!).

Como habrás adivinado, puedes aplicar el algoritmo de resolución de Pixelea para resolver este caso particular. Pero éste es mejorable, porque se realizan muchos movimientos extra. Así pues, tienes una oportunidad de encontrar una solución óptima.

Mi idea inicial era crear una versión del juego con dos colores con la intención de que la solución fuera del tercer color. También quería usar uno de los dos colores sólo en un cuadrado. Lamentablemente, ¡no es posible! Para ver por qué, usaremos un invariante por cambio de color. Pero primero vamos a tratar un problema relacionado: cómo saber el color final del rompecabezas.

El color final del rompecabezas

Un invariante es un valor asociado al estado de nuestro puzle (o a un sistema general) que es constante sin importar el estado del juego. Se trata de una potente técnica de resolución de problemas que de otra forma suelen ser complejos.

Vamos a crear un invariante que nos va a permitir calcular el color del tablero resuelto. Si asignamos valores enteros a, b, c a los tres colores (por ejemplo a = 0, b = 1 y c = 2), entonces podemos calcular la suma S de todos los valores de los colores del tablero. Resulta que el residuo de dividir S entre 3, llamémosle R, es un invariante. Esto significa que sin importar las veces que hagamos algún intercambio de colores, este valor es el mismo.

0
1
2
Asignamos un valor numérico a cada color. Podrían ser cualquier valor entero siempre que los residuos al dividir por tres fueran diferentes (para poder diferenciarlos). Lo más sencillo es escoger como valores los propios residuos 0, 1 y 2.

Usamos el invariante mezclado con congruencias: la aritmética de los residuos de divisiones. También se le conoce como aritmética modular, otra sencilla per eficaz técnica para resolver problemas difíciles. Pero no profundizaremos en ella. Sólo tener en mente que a partir de ahora: todos los números con el mismo resto al dividirlos por tres son iguales. Así que 42 = 0, 13 = 37 o 17 = 2.

Un estado cualquiera del rompecabezas Reto Pixelea.
Aquí tenemos 22 cuadrados grises, 18 azules y 24 naranjas. Usando los números asignados anteriormente a los colores, nuestro invariante es R = 18·0 + 24·1 + 22·2, es decir, R = 24 + 44 = 68. Pero recuerda, estamos trabajando con los residuos de 3. El residuo de 68/3 es 2, así que el invariante para esta imagen concreta del rompecabezas es R = 2.

¿Por qué es invariante R? Bueno deberíamos demostrar que cualquier intercambio de colores lo deja intacto. Veamos: un movimiento válido consiste en escojer dos cuadrados adyacentes de distinto color, pongamos x e y, y cambiarlos al tercer color, llamémosle w. Así que nuestro invariante después del movimiento es R' = R - x - y + w + w. La forma más fácil de ver que R' = R es explorar todos los casos. Recuerda que x, y, w son todos distintos. Resulta que sólo hay tres casos:

x y w 2·w - x - y Variación
0 1 2 2·2 - 0 - 1 0
0 2 1 2·1 - 0 - 2 0
1 2 0 2·0 - 1 - 2 0

La última fila contiene una variación de -3, que tiene residuo 0 al dividirlo por 3, así que equivale a 0. Por lo tanto, R es invariante.

Hemos visto que R es constante, por lo que será igual para todos los estados del rompecabezas. En particular, podemos calcularlo para el estado resuelto que tiene todos los cuadrados del mismo color. Si x es el color final, podemos calcular R sumando los 64 valores del color:

R = 64·x

Esto se puede expresar como:

64·x = (63 + 1)·x = 63·x + x

Pero 63 es múltiplo de 3, así que 63·x es multiplo de 3 y por tanto deja residuo 0, de forma que si trabajamos con los residuos,

64·x = 63·x + x = 0 + x = x

(En aritmética modular, diríamos que 64 es igual a 1 (residuo de 64/3), así que 64·x = 1·x = x)

Esto significa que si x es el color final, entonces R = x. En el ejemplo de la imagen anterior R valía 2, por lo que el color final para dicho rompecabezas era gris.

Resumiendo, el valor del invariante es el valor del color final. Para saber a qué color jugar simplemente calculamos la suma de los colores y dividimos por tres para quedarnos con el residuo. Sorprendentemente, la distribución de los colores sobre el tablero es irrelevante para el color final.

Reto Pixelea tiene color final naranja

Nuestra configuración consiste en 63 cuadrados azules y uno naranja. Independientemente de los valores asignados a los colores, como 63 es múltiplo de 3, los cuadrados azules equivalen a 0 en nuestro invariante, que pasa a ser el valor del único cuadrado restante, el naranja. Y esto significa que el color final del rompecabezas es naranja, no gris, que era mi intención.

Tablero azul con un cuadrado naranja.
Como hemos visto, el color final es naranja.

Ahora bien, si tuviéramos una configuración inicial con 62 cuadrados azules y dos naranjas entonces el color final sería distinto. Para esta distribución el invariante es, usando los valores de los colores previos, R = 62·0 + 2·1 = 2, así que el color final es gris.

Tablero azul con dos cuadrados naranjas.
También hemos visto que el color final aquí es gris.
Tablero azul con tres cuadrados naranjas.

Finalmente, para una distribución de tres cuadrados naranjas y el resto azul, el color final es azul. Como tenemos tres cuadrados naranjas y 3 es múltiplo de 3 y deja resto 0, éstos no afectan al valor del invariante. Quedan 61 cuadrados iguales (azules), y como 61 = 1, el invariante es el valor de un cuadrado azul, por lo que es azul.

Tablero azul con tres cuadrados naranjas.
La contribución de tres cuadrados del mismo color al invariante es cero. En este ejemplo, el color final es azul.

Créditos

Equipo

Componentes:

Comentarios (6)
  • · hace 12 meses

    Pixelea Challenge can be solved in 63 moves

    • · hace 12 meses

      Mi solución no queda registrada Edgar, saludos!

      • · hace 12 meses

        Hola Fali, sí, Alexey me ha comentado el mismo problema, trataré de resolverlo cuanto antes, saludos!

        • · hace 12 meses

          He realizado unos cambios, creo que ahora ya funcionará para quien sepa cómo resolverlo con 63 pasos!

        • · hace 12 meses

          Gracias Edgar!

          • · hace 12 meses

            As Alexey detected, there is a bug in the leaderboard: when you solve the puzzle more than once, it should pick the best result sorted by date! I've added it to the large bug list! Sorry for the inconveniences.

            Nuevo comentario

            Por favor, inicia sesión para poder comentar.