Cambalache 3,14 - La vidriera irrespetuosa

Algoritmo para resolver sudokus

Ha sido encontrado por Veit Elser, de la Universidad de Cornell, cuando estudiaba la manera de analizar amplitudes y ángulos de fase para generar imágenes 3D a partir de la microscopía por difracción aplicada a diminutos especímenes biológicos. Bloxito (nuestra fuente para esta noticia) afirma que se trata de un caso de serendipia.

Actualización: Bloxito también afirma que es el fin del sudoku, lo que es un poco exagerado, pues ya existían resolvedores de sudokus para prácticamente todos los cacharros con procesador disponibles.

Este algoritmo debe ser polinomial, mientras los anteriores no lo eran o debe bajar la complejidad. Desgraciadamente no he sido capaz de encontrar la referencia concreta ni, por supuesto, el algoritmo. Seguiremos atentos.

2006-03-10 18:31 | Categoría: | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/38139

Comentarios

De: lightme

Fecha: 2006-03-10 21:51

Me viene coo anillo al dedo ahora que me baje mi sudoku superkaramba :)

Por cierto esta entretenido el codenao

De: malambo

Fecha: 2006-03-10 23:37

Espera a dominar el algoritmo de Elser y verás como se tornan insoportablemente aburridos.

De: Zifra

Fecha: 2006-03-10 23:43

Malambo: ¿tienes alguna referencia del algoritmo?

No he logrado encontrar nada. Nada claro, al menos, referencias sí, pero no tengo ganas de "descifrarlo/traducirlo".

De: TaNk GiRL

Fecha: 2006-03-10 23:49

Por dios!
Dejadnos a la pobre gente de letras resolver nuestros sudokus inocentemente...
(Me hace ilusión, vale?)
:D

De: Zifra

Fecha: 2006-03-11 00:23

La noticia original que luego hemos copiado todos los demás no da pistas sobre el algoritmo.

El paper (PDF) de los rayos-X en biología no cita los sudokus.

Siempre puede uno estudiarse el algoritmo diference-maps con dos restricciones y aplicarlo a sudokus, pero me temo que tengo mejores cosas que hacer.

De: malambo

Fecha: 2006-03-17 02:23

No por lento, descortez. No Zifra, no he conseguido ninguna referencia específica de la aplicación del algoritmo del mapa de diferencias a los sudokus (mucho menos algún ejemplo) más allá que lo que cité en Bloxito. Para mi que se trata de algún aire de similaridad entre los problemas, pero sin aplicaciones concretas, aunque vaya uno a saber.