El enunciado de esta práctica está extraido del examen de la convocatoria
de septiembre de 2005. El tiempo estimado para la solución es entre una
hora y media y dos horas. Se deben entregar dos ficheros con nombres
checkRow.s y checkSquare.s (del que
se ofrece su estructura básica) que contengan las subrutinas
compruebaFila y compruebaCuadrado
respectivamente.
Para comprobar que la implementación de las rutinas es correcta se debe
utilizar el fichero sudoku.s. En él se ejecutan
un conjunto de pruebas. El ejecutable se obtiene mediante el siguiente
comando:
gcc -o sudoku sudoku.s checkRow.s checkSquare.s
Si la ejecución es correcta el programa debe imprimir el mensaje:
Ejecución aparentemente correcta
2. Comprobación de un tablero de Sudoku
El Sudoku es un puzzle de números basado en una matriz de 9x9. La única
regla para su solución es que en cada fila, cada columna y cada uno de los
9 cuadrados de 3x3 sólo pueden aparecer las cifras del 1 al 9 una sola
vez. La siguiente figura muestra un ejemplo de Sudoku ya resuelto.
Se puede comprobar que cada fila, columna y cuadrado de 3x3 incluye los
dígitos del 1 al 9 sin repetición. En el programa que comprueba la solución
del puzzle la matriz de números enteros está almacenada por filas. Se
necesitan implementar las siguientes subrutinas en ensamblador:
-
(20 puntos) Rutina compruebaFila: Recibe como parámetros a
través de la pila en posiciones ascendentes de
memoria la dirección de comienzo de una fila de la solución
y la dirección de comienzo de una tabla de 9 enteros inicialmente a
cero. La rutina devuelve a través de la pila el entero 1 si la fila
cumple el requisito de la solución, un 0 si no lo cumple, y un -1 si
tiene valores incorrectos (menor que 1 o mayor que 9). La siguiente
figura muestra cómo se almacenan los parámetros y el espacio para el
resultado en la pila justo antes de la llamada a esta subrutina.
La tabla de 9 enteros inicializados a cero se puede utilizar y
modificar sus valores para comprobar las veces que aparece cada
dígito. La solución debe realizar la comprobación utilizando un bucle.
Además, se ha implementado previamente la rutina todoIgual
que recibe como parámetro la dirección de una tabla con nueve enteros y
devuelve a través del registro %eax el valor 1 si todos
los elementos de la tabla son idénticos y 0 en caso contrario. La
rutina compruebaFila puede contar las apariciones de cada
dígito utilizando la tabla auxiliar y utilizar esta función para
comprobar que todos aparecen el mismo número de veces.
-
(20 puntos) Rutina compruebaCuadrado: Recibe como
parámetros la dirección del número que está en la esquina superior
izquierda del cuadrado y la dirección de una tabla de 9 enteros todos
ellos inicializados a cero. Devuelve en el registro %eax
el valor 1 si el cuadrado es correcto y cero en caso contrario. No
realiza ninguna otra comprobación de los valores numéricos de la
solución. La siguiente figura ilustra cómo están almacenados los
parámetros en la pila con respecto a un cuadrado de 3x3 enteros.
