Cómo generar un nuevo tablero de Sudoku válido

[Cactuss]

En la universidad me asignaron un proyecto para crear un juego de sudoku.
Me las he arreglado para hacer todo lo necesario, es un código bastante extenso ya que tiene que ser escrito todo en un solo script.
Mi problema no es, como podrán haberse imaginado, cómo resolver un sudoku dado, pues de esto hay suficientes métodos conocidos en internet y me las puedo apañar para implementar alguno de ellos. Mi problema es el siguiente: Debe haber una opción que me genere un nuevo tablero de sudoku con el que jugar.
Para esto pensé primeramente en generar un sudoku resuelto y luego eliminar casillas aleatoriamente. Sé que esto puede no generar un tablero válido (con solución única) en todos los casos, ese sería un problema. Pero el verdadero problema es que no puedo si quiera generar un sudoku resuelto.
Estuve buen rato intentando llenar casillas haciendo que el programa busque cuales son los números posibles en dicha casilla y colocar aleatoriamente cualquiera de estos números posibles. Pero se da el caso en algunas casillas del tablero donde no hay números posibles, pues al colocarse aleatoriamente los anteriores imposibilitaron a la casilla actual de poder llevar cualquier número. Para esto me las apañé demostrando cómo es posible en estos casos realizar permutaciones con otras casillas para resolver el problema, y así conseguí llenar 6 regiones (las regiones de 3x3) satisfactoriamente, pero al llegar a las últimas regiones las casillas no tenían números posibles y no conseguí patrón alguno para realizar permutaciones. Usando otro método similar conseguí llenar 7 regiones, pero las últimas dos restantes pues les pasó el mismo problema.
Sé que también se puede conseguir un tablero por fuerza bruta siguiendo ciertos métodos. Pero mi pregunta es: ¿Puede hacerse de forma lógica? Como lo que estaba intentando de realizar permutaciones cuando se encuentre con un caso inválido, o algo que siga ciertos pasos aplicables siempre.
Como habrán visto, esto es un problema de lógica y matemática, nada de código, quizá algo de pseudocódigo. Y es algo que me gustaría saber incluso aunque no pueda encontrar una solución lógica a tiempo para el proyecto. 

[javi in the sky]

Hola, un problema interesante el que planteas. En general lo que conozco y lo que he visto consultando implica que las soluciones para un sudoku se buscan mediante la técnica de algoritmia de "vuelta atrás" o backtracking en inglés, que viene siendo una especia de fuerza bruta guiada por una heurística. Si se determina que una solución no es viable en la búsqueda, se retoma la búsqueda en el último punto viable.

La propuesta que he encontrado sobre estrategia para generar tableros de sudoku aleatorios es esta que pongo a continuación aunque no sé si es válida.

ALGORITMO PROPUESTO PARA GENERAR TABLEROS SUDOKU ALEATORIOS

Segunda mitad del algoritmo (hacer que el tablero sea aleatorio y único)

1 Comenzar con un tablero completo y válido (lleno de 81 números).

2 Hacer una lista de las 81 posiciones de las celdas y mezclar aleatoriamente.

3 Siempre que la lista no esté vacía, tomar la siguiente posición de la lista y eliminar el número de la celda relacionada.

4 Probar la singularidad utilizando un solucionador de "vuelta atrás". Seremos, en teoría, capaces de contar todas las soluciones, pero para probar la unicidad, nos detenemos inmediatamente cuando encontremos que puede haber más de una solución.

5 Si la región 3x3 actual todavía tiene una sola solución, ir al paso 3) y repetir.

6 Si la región 3x3 actual tiene más de una solución, deshacer la última eliminación (paso 3) y continuar con el paso 3 con la siguiente posición de la lista.

7 Detenerse cuando se hayan probado las 81 posiciones.

Esto proporciona no solo tableros únicos, sino tableros en los que no se pueden eliminar más números sin destruir la singularidad de la solución.

Esta sería solo la segunda mitad del algoritmo. La primera mitad es encontrar primero un tablero válido completo (¡llenado al azar!) Se haría de manera muy similar, pero "en la otra dirección".

Primera mitad del algoritmo

1 Comenzar con un tablero vacío.

2 Agregar un número aleatorio en una de las celdas libres (la celda se elige al azar y el número se elige al azar de la lista de números válidos para esta celda de acuerdo con las reglas de SuDoKu).

3 Utilizar el solucionador de "vuelta atrás" para comprobar si la región 3x3 actual tiene al menos una solución válida. Si no es así, deshacer el paso 2 y repetir con otro número y celda. Tener en cuenta que este paso puede producir tableros válidos completos por sí solo, pero no son aleatorios de ninguna manera.

4 Repetir hasta que el tablero esté completamente lleno de números.