http://herraiz.org

En mi anterior entrada decía que los sudokus no eran más que sistemas de ecuaciones lineales sometidos a algunas restricciones, y que por tanto podría alcanzarse alguna solución (si existía) en un número finito de pasos. En caso de que no exista solución, también podría averiguarse ese hecho en un número finito de pasos. Sin embargo, Juan, mi compañero de piso, tras leer esa entrada me recordó que había olvidado un detalle: las soluciones de la ecuación tienen que ser enteras. Eso transforma en las ecuaciones en diofánticas; esto es, los coeficientes de las incógnitas son números enteros, y sus soluciones también.

En 1900, Hilbert, en su famosa conferencia exponiendo los 23 problemas que desafiaron a la matemática en el siglo XX, propuso como su décimo problema el demostrar si existe un modo de averiguar si una ecuación diofántica tiene solución en un número finito de pasos. La demostración de este problema fue negativa. Es decir, no existe un algoritmo para determinar si existe o no solución. La historia completa en el libro El reto de Hilbert, escrito por Jeremy J. Gray, que por cierto es profesor de matemáticas de la Open University.

Por tanto, no es posible determinar si un sudoku tiene o no solución.

Todavía no estoy muy convencido, porque el caso de los sudokus tiene una simplificación con respecto al décimo problema de Hilbert, y es que todas las ecuaciones son lineales. En El reto de Hilbert no se menciona que el décimo problema se haya demostrado afirmativamente para casos más simples (como el de ecuaciones lineales), así que me temo que es muy probable que no exista un algoritmo para determinar la resolubilidad de un sudoku.

En cualquier caso, esto no valida mi argumento acerca de que la gente resuelve los sudokus por evolución en vez de por métodos sistemáticos.