La clave de los sudokus con al menos una solución

Leo en Nature News que el matemático Gary McGuire cree haber encontrado la solución al número mínimo de casillas iniciales rellenas que debe poseer un sudoku resoluble de forma única. Concretamente, sugiere que es 17. El problema es equivalente al problema de conjunto de cobertura ya formulado por Karp como NP-completo. El código de búsqueda exhaustiva empleado puede descargarse aquí, así como el artículo. Cabe resaltar que el algoritmo ha requerido unas siete millones de horas de CPU en el centro de supercomputación de Dublín.

from Barrapunto http://ciencia.barrapunto.com/article.pl?sid=12/01/10/1717212&from=rss

Anuncios
Esta entrada fue publicada en Noticias y política. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s