Algoritmo «misterioso» que resuelve sudokus y nadie sabe cómo lo hace

Por Francisco R. Villatoro, el 24 diciembre, 2008. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Physics • Science ✎ 6

La ciencia te necesita. Tienes que ser tú quien descubra un sudoku que el programa «misterioso» no sepa resolver. Conéctate a la página web http://www.schaad.ca/hpr.html donde podrás rellenar tu sudoku. Si el programa lo resuelve (nadie sabe cómo lo hace), mala suerte. Si el programa no lo resuelve, habrás contribuido a que los investigadores logren entender cómo funciona el algoritmo «misterioso.» Nos lo cuenta Julie Rehmeyer, «The Sudoku solutionScience News, December 23rd, 2008 .

La vida da muchas vueltas, muchas vueltas da la vida. Nadie sabe cómo funciona un nuevo algoritmo para resolver problemas de restricción equilibrados. Dicho algoritmo es útil para diseñar telescopios y microscopios, para estudiar el plegamiento de proteínas, para mejorar los tratamientos del cáncer, e incluso para resolver sudokus.

El algoritmo «misterioso» fue descubierto/desarrollado en 1982 por el físico óptico James Fienup, de la University of Rochester. Ha recibido mucha atención tras ser presentado en una conferencia de óptica por el matemático Heinz Bauschke, de la University of British Columbia, y el físico teórico Veit Elser, de la Cornell University. Bauschke y Elser han aplicado técnicas de ingeniería inversa para tratar de entender el algoritmo y han descubierto que puede resolver problemas muy diversos con él, pero aún no han logrado entender cómo funciona. ¿Por qué molestarse? Porque, cuando funciona, es un algoritmo muy bueno y eficiente. En teoría, no siempre funciona, a veces, nunca para (entra en un bucle sin fin). Si se entendiera cómo funciona el algoritmo se cree que se podría mejorar y lograr que  parara siempre.

Elser y Bauschke creen que encontrar problemas en los que el algoritmo no pare será de gran ayuda para entender su funcionamiento. Por ello, Elser, Bauschke y su estudiante Jason Schaad han creado un programa online que te permite escribir un sudoku para retar al algoritmo «misterioso.» Hasta ahora ha resuelto todos los sudokus que se le han presentado. ¿Existirá algún suduku que no sea capaz de resolver? Los investigadores creen que sí. ¿Serás capaz de encontrarlo tú? Ánimo, prueba. 

Si no te ha tocado la lotería, quizás ahora te toque.



6 Comentarios

  1. creo que la respuesta al algoritmo esta en llevar un contador y a un acumulador para cada cuadro de nueve cuadritos de modo que le permita sumar los numeros y procesos necesarios en i para llenar el sudoku

  2. Amigos

    Tengo un programa que resuelve SUDOKUs, y en ocasiones la solucion no es unica. En las revistas de SUDOKUs, en los de gran dificultad mi programa encuentra en ocasiones, del orden de 2 ó mas soluciones independientes, por lo tanto, este algoritmo «misterioso», no tiene nada de «misterioso», es simplemente un algoritmo «simple» (como casí todos) de simulacion de inteligencia virtual.
    Saludos

    1. José, los sudokus difíciles normalmente tienen más de una solución, sobre todo cuando quien los publica no comprueba este desliz. Algunos «presumen» de que la dificultad está asociada a más de una solución. Diseñar un sudoku con muchas soluciones es muy fácil… pero en cierto sentido es hacer «trampa» al lector.

Deja un comentario