Por @Alvy — 15 de Noviembre de 2017

Puzzle Tetris

Andrea Iacono publicó un buen artículo sobre los algoritmos de «vuelta atrás»: Backtracking Explained. Se trata de una estrategia normalmente recursiva para resolver problemas como los de los laberintos, la colocación de piezas y similares, en los que mediante una búsqueda en profundidad se puede dar con la solución.

El nombre vuelta atrás (backtracking) viene del hecho de que en la búsqueda de la solución se va volviendo a un punto anterior para probar alternativas.

Backtracking

Imaginemos un laberinto: al llegar a una encrucijada (1, 2, 3) se prueba con una dirección. Si con eso se llega a la solución, problema resuelto. Si no, se vuelve atrás a la encrucijada anterior y se prueba con otra, repitiendo el proceso cuantas veces sea necesario. (Si se agotan todas las opciones y no se ha llegado, es que no existe solución: no hay salida)

Normalmente las combinaciones de este tipo de problemas son muchas, pero se aplican ciertas restricciones, lo que suele hacer el total de opciones a probar algo computable en un tiempo razonable. También se puede buscar revisar todas planteando obtener «una solución mejor»; de este modo se puede llegar a la solución óptima.

Algunos ejemplos típicos en los que se puede aplicar este método son los laberintos, el Sudoku (para uno normal de 9x9, entre 15.000 y 90.000 ciclos) o en ajedrez el problema del recorrido del caballo o el de las ocho damas. En terrenos más prácticos el problema de la mochila es uno de los ejemplos más clásicos: optimizar qué objetos meter que maximicen la ocupación de un espacio de una forma determinada (quizá lo hayas experimentado en el maletero del coche en los Tetris 3D de las vacaciones.)

El rompecabezas de madera de la imagen –uno de los muchos puzles de madera chinos sin nombre, similar al de los pentominós 2D– inspiró a Lacono a crear un programa para resolver llamado GoShapesPuzzle [en Github] usando el lenguaje Go (y gotk3), tal y como está explicado y en el código del que se puede aprender.

Compartir en Flipboard  Compartir en Facebook  Tuitear
Por @Alvy — 25 de Octubre de 2017

Muchas veces los grandes conceptos matemáticos se explican mejor con rompecabezas; encontrar la solución lleva a desarrollar herramientas, fórmulas o métodos de razonamiento que luego sirven para aplicar en otras áreas.

Este problema de los clavos y la cuerda es un gran ejemplo, y si no atención a la lista de asuntos implicados: teoría de grupos, conmutadores, simetrías, grafos de Cayley, bucles, generadores, fractales… Todo en 15 minutos de vídeo –con muy buenos subtítulos– que en absoluto resultan aburridos (dado que prácticamente se introduce un nuevo concepto cada minuto).

El problema consiste en enrollar una cuerda dándola vuelta en cierto número de clavos de modo que puedan sujetar en una pared un cuadro y que no se caiga, pero de modo que quitando cualquiera de los clavos todo el montaje se desmorone y el cuadro caiga por su propio peso. Aunque es fácil encontrar formas de hacerlo con pocos clavos el problema exige que funcione al quitar todos y cada uno de los clavos; el cuadro ha de caer siempre.

Quien desvela la solución al enrevesado asunto es Nakul Dawra de Gold Plated Goof, un canal relativamente reciente (tiene menos de un año) con contenidos altamente recomendables.

Dawra simplifica el problema a la situación con dos clavos y explica cómo crear una notación para las operaciones de «enrollado». Cada forma de enrollarlos (por larga y en revesada que sea) equivaldría a una fórmula, en cierto modo parecida a una multiplicación. Es fácil descubrir qué operaciones hacen que unos giros se cancelen con otros «desenrollando» la cuerda y volviendo a la configuración inicial (que equivale a «el cuadro cae»). Pero el orden en que se hacen los diversos giros influye, de modo que esos manejos no son conmutativos como en la multiplicación, sino algo un poco diferente.

Aquí es donde Dawra introduce la idea como parte de la teoría de grupos, algo que –como muchos aficionados conocerán– está en el corazón de rompecabezas como el cubo de Rubik y sus variantes, además de en otros órdenes de la vida.

La cosa puede complicarse tanto como sea necesario; de hecho en el rompecabezas planteado con clavos se puede demostrar que se puede utilizar cualquier número de clavos en el que se vaya enrollando la cuerda de forma enrevesada siempre que se combinen adecuadamente los conmutadores inversos que vayan revirtiendo los giros a cada paso. Esto hace que el resultado sea en cierto modo «muy satisfactorio e increíble» –al final del vídeo hay varios ejemplos– con decenas de clavos y una larga madeja de cuerda en la que el planteamiento original funciona y el «enredo imposible» desaparece.

Curiosamente si se desarrolla visualmente el problema de los clavos y la cuerda el resultado es un grafo de Cayley fractal – de ahí su infinitud y la propiedad de que si se construye correctamente ese serpenteante camino de cuerda el problema tiene una elegante solución.

Compartir en Flipboard  Compartir en Facebook  Tuitear
Por @Alvy — 24 de Octubre de 2017

En esta pequeña pieza de Great Big Story el arquitecto húngaro Ernő Rubik cuenta algunas historias sobre cómo inventó y resolvió el rompecabezas mecánico en forma de cubo que inventó a mediados de los años 70.

Según explica la idea le sobrevino hacia 1974 mientras impartía clases de arquitectura e imaginaba un objeto simple pero a la vez artístico. Cuando vio que el cubo que había ideado –lo más complicado fue el mecanismo, naturalmente– era a la vez un rompecabezas lo patentó en su Hungría natal (patente HU170062).

El cubo era relativamente fácil de fabricar de modo que a finales de 1977 ya se estaba vendiendo en las tiendas como juguete. Un par de años después Rubik llegó a un acuerdo con Ideal Toys y entre 1979 y 1980 comenzó a distribuirse internacionalmente. Hoy en día se considera uno de los juguetes más vendidos de todos los tiempos y el típico objeto que está en prácticamente cualquier hogar.

El problema para Rubik era que cuando mezcló el cubo por primera vez no había manuales, ni páginas web ni libros ni tutoriales de YouTube que explicaran cómo resolverlo. ¿Cómo pudo resolverlo entonces?

Dice que examinando su funcionamiento desde el punto de vista matemático pudo dar con una solución al cabo de un mes; solución que ni siquiera era óptima y directa, aunque cumplía con su tarea.

Hoy en día el récord del mundo para resolver ese mismo cubo de Rubik de 3×3×3 sigue en 4,69 segundos, en manos de Patrick Ponce desde el 2 de septiembre de 2017.

Compartir en Flipboard  Compartir en Facebook  Tuitear
Por @Alvy — 14 de Agosto de 2017

La escalera que no puede existir… ¿O sí?

Genious Puzzles tiene esta escalera que no puede existir: aunque a simple vista todo parece perfectamente claro y lógico si te pones a subir o bajar escalones algo no cuadra.

El caso es que hay dos niveles de diferencia entre las escaleras de uno y otro lado, y como todas parecen acabar al mismo nivel… Definitivamente esto no puede existir. Es algo más propio de M.C. Escher (Ascendiendo y descendiendo, Cascada) que de un escenario lógico donde se respeten las reglas de la geometría.

Quizá lo más parecido sería la Escalera de Schoeder, aunque en vez de escalones enlazdos aquí los pasillos se alargan para complicarlo un poco más. A mi me recuerda a los escenarios isométricos de Realm of Impossibility, de Mike Edwards y Electronic Arts, uno de mis juegos favoritos para C-64.

¿Tiene solución problema este problema visual? Si se abre la mente se puede dar con una figura equivalente que se podría construir en la realidad. Recordemos que estas imágenes utilizan trucos forzadas y que lo que parece un camino se puede cortar en algunos puntos. Todo es cuestión de encontrar donde. Aquí podría ser en la unión de la escalera de arriba a la izquierda. Pero las tonalidades de color que tienen continuidad complican el asunto. Así que la solución sería «convertirlas» visualmente en formas planas, recortadas de forma precisa para que encajaran visualmente en las líneas negras. De este modo toda la escalera estaría en el aire hasta cierta altura, pero la parte superior más clara no se separaría nunca del anillo cuadrado que rodea el escenario. En cierto modo, la escalera… sí podría existir.

(Vía @pickover.)

Compartir en Flipboard  Compartir en Facebook  Tuitear