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 flojo
en el renglón R y la columna C que está obligado a saltar
a cuadros que no ha visitado. Como el caballo es flojo, la idea es
buscar un recorrido en el cual se atore en tan pocos saltos como sea
posible. Escribe un programa llamado flojoZZ (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
la posición inicial (R, C) del caballo (con 1 <= R, C <=
N) y que escriba como salida el
recorrido buscado del caballo. 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 no visitadas se indican con un 0. En el ejemplo mostrado
(que no necesariamente es el mejor) el caballo visita 9 cuadros y
allí se queda atorado, pues los dos saltos posibles ya han sido
visitados antes (el 6 y el 8).
| Ejemplo de entrada |
Ejemplo de salida |
| 4 2 2 |
7 4 0 2 0 1 6 0 5 8 3 0 0 0 0 9 |
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 hay un caballo supersticioso en el renglón R y la columna C que tiene un número M de mala suerte. Como el caballo es supersticioso, la idea es buscar un recorrido en el cual visite (sin repetir ninguno) tantos cuadros del tablero como pueda, excepto aquellos cuyas coordenadas (X, Y) sumen un múltiplo de M. Escribe un programa llamado malasZZ (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), la posición inicial (R, C) del caballo (con 1 <= R, C <= N) y el número M (con 2 <= M <= 2N) y que escriba como salida el recorrido buscado del caballo. Puedes suponer que R+C no es divisible entre M. 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 no visitadas se indican con un 0. En el ejemplo mostrado (que no necesariamente es el mejor) el caballo visita 8 cuadros y allí ya no puede avanzar más, puesto que los dos saltos posibles lo llevan a un cuadro ya visitado (el 7) o a un cuadro de mala suerte (3+3 = 6, un múltiplo de M).
| Ejemplos de entrada |
Ejemplos de salida |
| 4 1 3 3 |
0
0 1 0 0 7 4 0 5 2 0 0 8 0 6 3 |
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.