UEA: Diseño de Algoritmos
Trimestre: 2007 Invierno
Entrega: 2 de marzo de 2007 a las 10pm

Problema 1: Diseñe un algoritmo usando la técnica de búsqueda con retroceso para resolver el siguiente problema: Sea N un entero positivo y considere un tablero de ajedrez de N por N en el que se desean colocar reinas idénticas de forma tal que éstas ataquen todas las posiciones del tablero (no importa si las reinas se atacan entre sí o no). Su algoritmo deberá encontrar el mínimo número K de reinas que satisfacen esta condición y deberá calcular el número F de formas distintas se puede realizar. Observe que K <= N. Por ejemplo, si N = 2 entonces K = 1 y F = 4. Escriba un programa llamado ataca basado en su algoritmo que acepte como entrada el entero positivo N y que escriba como salida los números K y F en ese orden. De nuevo, si la entrada fuera 2 entonces la salida debe de ser 1 4. Puede suponer que 1 <= N <= 20.

Problema 2: Diseñe un algoritmo usando la técnica de búsqueda con retroceso para resolver el siguiente problema: Dados tres enteros positivos N, A y B considere un tablero de ajedrez de N por N en el que hay un caballo en la posición (1, 1) que se quiere hacer llegar a la posición (N, N). Este caballo puede brincar A cuadros en cualquier dirección paralela a los lados del tablero y luego B cuadros en cualquier dirección perpendicular a la anterior (un caballo del juego de ajedrez normal tiene A = 2 y B = 1). Su algoritmo deberá encontrar el mínimo número P de pasos que se necesitan para lograr el objetivo. Observe que P <= N². Por ejemplo, si N = 4, A = 1 y B = 2 entonces P = 2. Escriba un programa llamado acaba basado en su algoritmo que acepte como entrada tres enteros positivos N, A y B en ese orden y que escriba como salida el número P. De nuevo, si la entrada fuera 4 1 2 entonces la salida debe de ser 2. Puede suponer que 1 <= N <= 20, que 1 <= A <= N, que 1 <= B <= N y que el objetivo se puede lograr.