Por @Alvy — 11 de Diciembre de 2017

Este cubo de Rubik de 33×33×33 es tan grande como titánicamente cafre: fabricado con 6.153 pequeñas piezas su precio es de unos 15.000 euros, pero no basta con soltar la pasta: encima hay que esperar 3 meses a que lo impriman en 3D (25 horas) y te lo monten (200 horas). Lo venden en Oliver Stickers.

El colmo es que sus caras ni siquiera parecen girar muy bien y hay que manejarlo con un refajo para que no se rompa. Además dicen que el pestazo que sueltan los productos químicos que hay que usar tira para atrás y que después de manejarlo un poco acabas con las manos negras. ¡Todo por la causa rompecabecística!

Relacionado,

Compartir en Flipboard  Compartir en Facebook  Tuitear
Por @Alvy — 22 de Noviembre de 2017

Sudoku constraint propagation

Aunque los populares sudokus se pueden resolver de muchas formas, que lo haga un ordenador no siempre es tan fácil como parece. En How To Win Sudoku Grant Bartel explica cómo funciona un método «típico de la inteligencia artificial» para hacerlo – lo cual aunque suene grandioso en realidad está al alcance de muchos programadores. Se trata de un algoritmo de propagación con restricciones, una técnica que se suele utilizar en problemas combinatorios.

Se trata de un método que permite dirigir el programa hacia una solución probable («propagar») mientras sigue las reglas de un cierto espacio y los valores posibles a utilizar por ciertas variables en dicho espacio («restricciones»).

El artículo explica el procedimiento paso a paso y cita el trabajo de Peter Norvig Solving Every Sudoku Puzzle que fue el primero que describió cómo utilizar esta técnica para resolver sudokus mediante propagación con restricciones con búsqueda en profundidad en un árbol binario de búsqueda.

Pero esta no es la única forma de resolver un sudoku. Hay muchos otros métodos para resolver sudokus, en especial los algoritmos de vuelta atrás (backtracking), los de búsqueda estocástica (rellenando las casillas al azar, contando los errores y reduciendo el número de errores hasta llegar a cero) o mediante un algoritmo de cobertura exacto.

Compartir en Flipboard  Compartir en Facebook  Tuitear
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