Su Doku es un juego muy conocido, no entraré en detalles históricos. Este problema puede ser visto como el problema de colorear un grafo, de esta forma los colores son cada uno de los números del uno al nueve, los nodos son cada una de las casillas y están conectados si están en un mismo recuadro, en una misma fila o en una misma columna.
Pasando a la solución por backtracking bien se puede ver que la fuerza bruta consiste en ubicar las casillas vacias y poner un numero en cada una de ellas y ver cuando ya no hayan casillas vacias si el sudoku ha sido resuelto, de no ser así se vuelve a atrás y se intenta con otros números. El problema de este enfoque es que si hay n casillas vacías se tendrán n! (n factorial) formas de llenar estas casillas. Tal vez para unas 9 casillas vacías funcione, pero si se intenta con 10 o más en un ordenador común en la actualidad, puede tardar mucho tiempo.
Así que la mejor forma de hacerlo es ver cuál casillas de las vacías tiene menos posibilidades y optar por una de ellas y hacer lo mismo recursivamente hasta que no hayan casillas vacías, en este punto se verifica si el sudoku está bien, de ser así ya está, si no entonces se vuelve atrás y se opta por otra de las posibilidades en la casilla que tenia varias posibilidades. Finalmente, si el sudoku está bien construido se podrá llegar a una solución.
En pseudocódigo esto podría ser algo como (la implementación en java o cpp no va más de 80 líneas! :) )
Creo que esta es la forma mas simple de resolver este problema, otro enfoque es usando la ténica de Knuth de "Dancing links". El enfoque presentado aquí no es el más eficiente pero es bastante sencillo de programar y puede ser útil en un concurso de programación :)
Cualquier comentario o duda, comenten.
Nota: les dejo algunos problemas que se pueden resolver con este algoritmo.
https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2246
http://projecteuler.net/problem=96
