Feliz Año Nuevo!

Otro año más y uno de mis propósitos es el mantener este blog updateado porque estuvo el pobre abandonado un rato. Aprovecho para pedir al universo que aquéllos que desarrollan el BlogPress para iPhone, lo mejoren para que permita escribir en html, porque de plano el formato de texto sin justificar me choca.

Voy a empezar este mes con un post bastante ñoño. Verán. Mi amiga V me avisó que había una competencia en la página de una bailarina que nos gusta mucho (sí, sí, sí...ya sé que el otro blog es para ballet, pero ese no es el punto de este post). El premio son unas zapatillas autografiadas y un DVD que no tengo del Lago de los Cisnes (porque los méndigos son carísimos). Para ganar uno debe resolver un rompecabezas de esos que uno va deslizando las fichas en un cuadrado. El que lo haga en el menor número de movimientos y en el menor tiempo gana el premio.

V básicamente me mandó a resolverlo, jejeje y yo fuí a hacer mi mejor esfuerzo. El rompecabezas del que hablamos, es de 15 piezas (cuadrícula 4x4) y mi gran récord fue de 534 movimientos en 753 segundos. Bastante mediocre.

Luego se me ocurrió preguntarme cuál sería el número de movimientos mínimo para resolver este problema? Pensé - Este es el típico problemita de Matemáticas Discretas y seguramente debe de haber algún teorema en el que se pruebe cuál es su complejidad, etc.-.

Resulta que es un problema clásico y hay varios teoremas relevantes a sus soluciones y demás. Encontrar soluciones es fácil pero el problema de encontrar la solución más corta es duro (NP-duro), y para el caso de 15 piezas, una solución aceptable tiene de 0-80 movimientos. Como pueden ver, mi solución anterior fue nefasta.

Para poder mejorar mi récord (y ganarme el premio...yay!), decidí tratar de ver si podía hacerme de un método para encontrar una mejor solución, y como siempre, es mejor simplificar el problema, esto es, partir el problema en problemitas.