PDF de programación - MEMORIA DE LA PRÁCTICA DE PROGRAMACIÓN III CURSO 2005-2006

MEMORIA DE LA PRÁCTICA DE

PROGRAMACIÓN III

CURSO 2005-2006

DIEGO J. SÁNCHEZ CAAMAÑO, DNI: 12385191-J

CENTRO ASOCIADO DE ALBACETE

Índice

1. RESPUESTAS A LAS CUESTIONES PLANTEADAS EN EL ENUNCIADO................................ 3

1.1 Descripción del tipo de problema y esquema algorítmico utilizado.............................................. 3

1.2 Estrategias locales consideradas en la asignación de valores. Condiciones de poda..................... 5

1.3 Análisis del coste en términos de trazabilidad computacional.......................................................6

2. EJEMPLO DE EJECUCIÓN PARA EL CASO DE PRUEBA............................................................7

3. ESTUDIO DEL COSTE DEL ALGORITMO....................................................................................12

4. LISTADO DEL CÓDIGO FUENTE COMPLETO............................................................................13

Clase Sudoku...................................................................................................................................... 13

Clase Resuelve....................................................................................................................................14

Clase TipoSudoku.............................................................................................................................. 17

Clase Traduce..................................................................................................................................... 22

2 de 25

1. RESPUESTAS A LAS CUESTIONES PLANTEADAS EN EL ENUNCIADO.

1.1. Descripción del tipo de problema y esquema algorítmico utilizado.

a) Descripción del problema y elección razonada del tipo de algoritmo.



El Sudoku requiere para su resolución el rellenado de una matriz de 9 * 9 casillas con valores
entre 1 y 9, respetando tres reglas: no debe haber valores repetidos ni en las filas, ni en las
columnas, ni en los nueve bloques de 3 * 3 en que se divide la cuadrícula.

Este tipo de problema no permite su descomposición en problemas de menor tamaño, ya que el
valor introducido en cada casilla influye en el resto de ellas, al no poder repetirse. Se descarta,
por tanto, un esquema tipo Divide y Vencerás.

Aparentemente se podría resolver mediante un algoritmo Voraz que comprobase que cada valor
que se introduzca en la matriz cumple las tres reglas básicas. Esto es posible en los ejemplares
simples del problema, en los que la aplicación de estas reglas va dejando un sólo valor posible
en algunas celdas, que al ser rellenadas provocarán a su vez que otras casillas tengan sólo un
valor posible, y así hasta el llenado completo de la matriz. Pero hay ejemplares complejos que
tras la aplicación de las tres reglas dejan las casillas vacías con al menos dos valores igualmente
posibles, con lo que no hay forma de prever que podamos cometer un error en la elección de un
valor que nos conduzca a una situación sin solución, con una o más casillas sin candidatos
posibles. De ser ese el caso, nos veríamos obligados a deshacer una decisión tomada.

El problema se puede asimilar a un árbol que tenga como raiz un Sudoku parcialmente relleno
(en nuestro caso pasado mediante un fichero o la entrada estándar), y cuyas ramas sean los
Sudokus con una casilla más rellena. En cada nodo habrá 9 ramas, al ser esos los posibles
valores que piede adoptar cada casilla. La solución será la hoja de profundidad '81 – el número
de casillas rellenas inicialmente' que esté completada con valores que cumplan las tres reglas.

Inicialmente el árbol no está completo (el Sudoku inicial sólo está parcialmente relleno), por lo
que hay que irlo construyendo a medida que se explora.

Por todo lo anterior, el esquema correcto es el de Vuelta Atrás, que recorre el árbol mientras se
construyen soluciones parciales, y permite deshacer una decisión tomada que no nos conduzca a
la hoja solución.

b) Descripción del esquema algorítmico usado e identificación con el problema.



El esquema general de Vuelta Atrás es el siguiente:

Algoritmo Vuelta Atrás

fun vueltaAtras (ensayo)

si válido (ensayo)
entonces dev ensayo
si no para hijo

Є

compleciones (ensayo)

hacer

si condiciones de poda (hijo)
entonces vueltaAtras (hijo)

fsi

ffun

3 de 25

En nuestro caso, un ensayo es válido si está completo, es decir, si tiene 81 casillas rellenas
correctamente. El ensayo inicial tendrá un número x de casillas rellenas, dependiendo de la
matriz de entrada. En cada llamada a compleciones se crearán ensayos con x+1 casillas rellenas,
tantos como posibles valores pueda adoptar la casilla a rellenar.

En la comprobación “si condiciones de poda (hijo)” se realiza la llamada recursiva si el candidato
cumple las condiciones de poda, para continuar con la generación del árbol. En caso contrario,
el algoritmo realiza la vuelta atrás: descarta ese camino y retrocede a la última bifurcación para
continuar con otro hijo. Si no hubiera más hijos, retrocedería hasta el anterior nodo y buscaría
otro camino. En caso de tener que retroceder hasta la raíz, el algoritmo finalizaría al no
encontrar la solución.

Algoritmo Compleciones

Es el algoritmo encargado de ir creando el árbol. Devuelve una lista con los hijos del nodo
(ensayo) que se le pasa. El esquema general puede ser el siguiente:

fun compleciones (ensayo)

lista ← lista-vacía
si condiciones de poda (ensayo)

entonces hacer

para cada valor válido hacer

hijo ← generar ensayo(valor)
lista ← insertar (hijo)

fpara

fsi
dev lista
ffun

Para limitar la anchura del grafo creado y facilitar la búsqueda de la hoja solución, generaremos
nuevos ensayos sólo con valores posibles en la casilla a tratar; llamamos valor posible al que
cumple con las tres reglas de la definición del Sudoku, reflejadas en las condiciones de poda.
Por ello la comprobación “si condiciones de poda (ensayo)” de la cuarta línea se puede eliminar
por redundante.

Sin perder generalidad podemos afirmar que a efectos de estudio del algoritmo es irrelevante la
posición de la casilla a rellenar, por lo que si elegimos para ello la casilla con menos candidatos
no desvirtuamos el mismo, simplemente decidimos qué rama queremos desarrollar en cada
pasada. Esta elección permite restringir aún más la anchura del grafo, agilizando así la búsqueda
de la solución, al crear en cada pasada el menor número de hijos posibles.

El algoritmo adaptado queda así:

fun compleciones (ensayo)

lista ← lista-vacía
casilla ← localiza_mejor (ensayo)
para cada valor posible en casilla hacer

hijo ← generar ensayo(valor)

lista ← insertar (hijo)

fpara
dev lista

ffun

La llamada “generar ensayo(valor)” realiza la inserción del dato pasado en la posición
anteriormente calculada (casilla).

4 de 25

Estructuras de datos.

Para la implementación del esquema general, definimos los siguientes elementos:

Una clase TipoSudoku, que representa la matriz completa, con estos atributos:

➢ Una subclase Numero, que representa cada una de las 81 casillas, con estos

atributos:
•
• Un booleano que indica si la casilla tiene valor asignado.
• Una lista que contenga los valores posibles de la casilla, según las tres

El valor de la casilla (0 si no está definido).

reglas, actualizable cada vez que se inserte asigne valor a una casilla.

➢ El número total de casillas rellenas.
➢ La matriz de casillas de tipo Numero.

Las funciones que permiten el trabajo con la matriz:

➢ Creación, copia y consulta de datos de una matriz.
➢ Consulta, inserción y borrado de datos en una casilla.
➢ Comprobación de cumplimiento de las tres reglas (poda).
➢ Descarte de valores posibles de cada casilla.

Y unas clases generales:

Clase Sudoku, clase principal del programa, que gestiona los atributos de la llamada inicial.

Clase Resuelve, que contiene y controla los algoritmos para la resolución del problema: Vuelta
Atrás, Compleciones y otros auxiliares.

Clase Traduce, que se encarga de la recepción, filtrado y “traducción” de los datos iniciales, ya
sean provinientes de la entrada estándar como de un fichero.

1.2. Estrategias locales consideradas en la asignación de valores. Condiciones de poda.

Las condiciones de poda se reducen a aplicar las tres reglas básicas del Sudoku y una
comprobación de los valores posibles en cada casilla, esto es:

➢ No se repiten valores en una fila.
➢ No se repiten valores en una columna.
➢ No se repiten valores en un bloque.
➢ No hay casillas vacías sin candidatos posibles.

Al tener una lista de candidatos en cada casilla, las condiciones de poda se traducen en la
actualización de los candidatos tras rellenar cada casilla. Además se realizará una comprobación
de que ninguna casilla vacía se ha quedado sin candidatos tras cada actualización, caso que
denotaría un camino sin solución y produciría una vuelta atrás.

5 de 25

En la clase TipoSudoku, los métodos encargados de aplicar las tres reglas son quitaCandidatos
(aplicado en la primera comprobación de la matriz de entrada, reduce los candidatos de todo el
Sudoku) y quitaCandidatosTrasPoner (llamado tras la introducción de un dato, sólo revisa los
candidatos de la fila, columna y bloque influidos por la casilla rellena).

El método condicionesDePoda, llamado desde el algoritmo Vuelta Atrás, es el encargado de
realizar la comprobación de que no haya casillas vacías sin candidatos posibles.

1.3. Análisis del coste en términos de tratabilidad computacional.

Intentaremos demostrar la tratabilidad del problema estudiando el peor algoritmo posible, un
recorrido secuencial de la matriz aplicando en cada casilla todas las combinaciones posibles.

Hay n * n casillas, cada una con n valores posibles. Para rellenar cada una de ellas, debemos
cumplir las tres reglas del sudoku, que limitan los valores posibles dependiendo de las casillas
ya ocupadas. Eso se realiza compro