Reincidir

Yo se que habia prometido reformarme y no escribir cosas como esta y la que le precede, pero como todo adicto, no pude evitar reincidir; ahora estoy intentado por todos los medios NO escribir este post, pero estoy perdiendo la batalla.

Las reglas del Sudoku son muy simples, la foto del post anterior las describe, sin embargo, el juego resulta ser mas complicado de lo que podria esperarse. En primer lugar, el problema general de resolver un sudoku de n^2 x n^2 es NP-completo. No todo esta perdido, pues hay un automata finito determinista que lo resuelve.

En aspectos mas combinatorios de la teoria, solo se sabe cuantas cuadriculas admisibles de 9 x 9 existen, nadie sabe el numero de cuadriculas admisibles de 16 x 16. Otra pregunta interesante es cual es el numero minimo de casillas que hay que llenar para conseguir un sudoku con solucion unica, en el caso de 9 x 9 es obvio que se necesitan al menos 8, y el ejemplo con el menor numero de casillas llenas que da una solucion unica que se ha encontrado contiene 17 numeros.

Referencias Bibliograficas:
Comunicacion personal del autor con otros estudiantes.
Seminario de Combinatoria, Royal Holloway, University of London.