Pseudocodigo Para Algoritmo De Ajedrez 4f4i1r

Andres Felipe Herrera Buitrago Universidad Javeriana Análisis de Algoritmos

ALGORITMO Y DISEÑO - PROBLEMA DE LAS (N) REINAS Problema Determinar si es posible posicionar un numero N de reinas en un tablero normal de ajedrez (8x8) sin que estas se amenacen.

Contexto Un tablero normal de ajedrez se compone de una cuadricula de 8x8 La reina dentro del ajedrez puede moverse únicamente en línea recta ya sea a través de las columnas, filas o diagonales del tablero, tal como lo muestra la ilustración en la cual el punto rojo representa a la reina y las líneas rojas representan los posibles movimientos de la reina

Se considera que una reina está amenazando a otra si esta está en la misma fila, columna o diagonal que la otra.

Análisis Entradas: El algoritmo debe recibir un numero entero N positivo mayor a 0 indicando el número de reinas de las cuales se quiere saber si es posible posicionarlas sobre el tablero sin que se amenace Salidas: El resultado de el algoritmo debe ser un mensaje afirmativo con una lista de las posiciones de cada reina en el tablero en caso de ser posible o un mensaje negativo si no es

posible Cada reina debe estar en una columna, una fila y una diagonal diferente a las otras. por lo cual podemos concluir que el número máximo de reinas que se pueden colocar en un tablero 8x8 son 8 reinas. Por lo tanto, si el número de reinas ingresado es mayor a 8 no es posible acomodar las N reinas dentro del tablero se deberá terminar el algoritmo y dar un mensaje negativo Si el número es menor o igual a 8 si es posible acomodar las reinas

Solución Si el numero ingresado N es una entrada valida se verifica si es mayor a 8, en caso de ser mayor a 8 se da un mensaje negativo inmediatamente de lo contrario se empiezan a acomodar las reinas dentro del tablero, Para acomodar cada reina sin que este amenazando se van a utilizar 4 estrategias 1.Se les dará un índice a todas las columnas del 1 al 8 2.Se les dará un índice a todas las diagonales descendentes del -7 al 7 3. Se les dará un índice a todas las filas del 1 al 8 4. Se lleva un contador C de las reinas que han sido ubicadas Las posiciones de las reinas se darán en forma cartesiana (x,y) donde X es la fila y Y es la columna Cada posición de las reinas se guardará en una lista de coordenadas la cual se mostrará en la salida del algoritmo 1.La primera reina se coloca en una posición aleatoria dentro del tablero seleccionando dos números (x,y) aleatoriamente entre 1 y 8, uno para su fila y otro para su columna, dicha posición se guarda en la lista de posiciones, se elimina X del índice de las filas y se elimina Y índice de columnas, además de esto se realiza la operación X-Y=K y K se elimina del índice de diagonales 2.Para posicionar las siguientes reinas se verifica si C es menor a el numero N de reinas ingresado, en caso de ser menor se pasa al paso 3 en caso contrario se pasa al paso 5 3.Se escogerá el primer número dentro del índice de filas el cual será X, luego con el índice de columnas se hará la operación X-(índice de columna)=W con cada número en el índice, Hasta que se encuentre un W que este en el índice de diagonales, se toma entonces el índice de columna como Y y se procede a eliminar X del índice de filas, Y del índice de columnas y W del índice de diagonales 4.Se le suma 1 al contador C y se regresa al paso 2 5. se da la lista de posiciones de las reinas y finaliza el algoritmo

Pseudocódigo Entrada: Entero N>0 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29.

Cadena Mensaje=”” Si N > 8 Mensaje=“No es posible” y se finaliza el algoritmo Mensaje=”Si es posible” int C=0 int B=0 int K=1 Lista de enteros IC= {1,2,3,4,5,6,7,8} Lista de enteros IF= {1,2,3,4,5,6,7,8} Lista de enteros ID={-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7} Int X=entero aleatorio ∈ [1,8] Int Y=entero aleatorio ∈ [1,8] (X,Y) se guarda en lista de posiciones X se elimina de IF Y se elimina de IC W=X-Y W se elimina de ID C=C+1 Si C>=N Finalizar algoritmo X=primer elemento de IF B= elemento [K] de IC Si X-B no se encuentra en ID, K=K+1 regresar al paso 20. Y=B (X,Y) se guarda en lista de posiciones X se elimina de IF Y se elimina de IC W=X-Y W se elimina de ID K=1 Regresar al paso 17.

Salida: Lista de posiciones y Mensaje