Todos sabemos lo que el Sudoku es. Dado un rompecabezas de Sudoku, se puede utilizar un simple procedimiento recursivo para resolver utilizando una computadora. Antes de describir el algoritmo, hacemos algunas definiciones.
Una solución parcial es un rompecabezas de Sudoku con sólo algunos de los números introducidos.
Dado un cuadrado vacío en una solución parcial, una asignación de un dígito a la plaza, es consistente si no aparecen en la misma fila, columna o $3\times 3$ plaza.
El algoritmo es como sigue:
- Si hay alguna plaza para la que no existe una asignación, a renunciar.
- De lo contrario, elegir una plaza vacía $S$ (*).
- Calcular el conjunto de todas las asignaciones consecuentes $A$ a esta plaza.
- Ir a través de todas las asignaciones $a \in A$ en un cierto orden (**):
- Poner $a$$S$, y recurse.
Tenemos dos grados de libertad: la elección de una plaza vacía, y la elección y el orden de las asignaciones a la plaza. En la práctica, parece que sea cual sea la elección, el algoritmo llega a una solución muy rápida.
Supongamos que le damos el algoritmo de un parcial de Sudoku con una única solución. Puede que ataba el número de pasos que el algoritmo necesario para encontrar la solución?
Para hacer la vida más fácil, usted puede elegir cualquier regla que ustedes deseen ( * ) y (**), incluso un azar de la regla (en ese caso, la cantidad pertinente es, probablemente, la expectativa); cualquier analizables elección sería interesante.
También, si ayuda, puede suponer algo acerca de la entrada - decir que al menos $X$ plazas se llenan. También estoy dispuesto a relajar la restricción de que hay una solución única - de hecho, incluso con un tablero vacío, el algoritmo anterior se encuentra una completa Sudoku muy rápido. Analiza por azar entradas (en cualquier sentido) también son bienvenidos.
