Trimestre 2010 Primavera
Entrega: 31 de mayo de 2010 a las 22:00.
Problema
1: Diseña un algoritmo usando la técnica de
búsqueda con retroceso para resolver el siguiente problema: se
tiene un tablero de ajedrez de N por N en el cual hay un caballo que
debe visitar todas las posiciones permitidas (sin repetir ninguna) y
evitar todas las posiciones prohibidas. Escribe un programa llamado caballoZZ (donde ZZ es una clave de
dos
dígitos asignada por el profesor) basado en tu algoritmo
que acepte como entrada un entero positivo N (con 1 <= N <= 20) y
una descripción del tablero y que escriba como salida el
recorrido buscado del caballo. En la entrada el tablero se describe por
una matriz de N por N donde cada entrada vale 0 si está
prohibida, 1 si está permitida y 2 si allí está el
caballo. Puedes suponer que hay exactamente un caballo y que existe al
menos un recorrido que cumple las propiedades pedidas. En la salida el
tablero se describe por una matriz de N por N donde las posiciones
sucesivas del caballo se numeran como 1, 2, ..., N2 y las
posiciones prohibidas se indican con un 0.
Ejemplo de
entrada
Ejemplo de
salida
4
1 1 1 0
1 1 1 0
1 1 2 1
0 1 1 1
11 2 7 0
8 5 10 0
3 12 1 6
0 9 4 13
Problema 2: Diseña un
algoritmo usando la técnica de búsqueda con retroceso
para
resolver el siguiente problema: se tiene un tablero de ajedrez de N por
N en el cual se deben colocar N reinas en las posiciones permitidas
(sin que se ataquen entre sí) evitando poner reinas en las
posiciones prohibidas. Escribe un programa llamado reinasZZ (donde ZZ
es una clave de
dos
dígitos asignada por el profesor) basado en tu algoritmo
que acepte como entrada un entero positivo N (con 1 <= N <= 20) y
una descripción del tablero y que escriba como salida la
posición buscada de las reinas. En la entrada el tablero se
describe por una
matriz de N por N donde cada entrada vale 0 si está prohibida y
1 si
está permitida. Puedes suponer que existe al menos una forma de
colocar las reinas que cumple
las propiedades pedidas. En la salida el tablero se describe por una
matriz de N por N donde las posiciones de las reinas se marcan con un 1
y las demás posiciones se marcan con un 0
Ejemplo de
entrada
Ejemplo de
salida
4
1 0 1 0
1 1 0 1
0 1 1 1
0 1 0 1
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
Notas: Tus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado. El
tiempo de ejecución de sus algoritmos será considerado
como parte de la evaluación.