====== Examen Final - 75.23. Inteligencia Artificial ====== **Cátedra:** Cabrera\\ **Fecha:** Primera Oportunidad - Segundo Cuatrimestre 2006\\ **Día:** 14/12/2006 Esta página está incompleta; podés ayudar completando el material. ===== Enunciado ===== ==== Punto I ==== Desarrollar un programa en prolog que, dadas por parámetro las dimensiones de un tablero, y una cierta cantidad de obstáculos, mueva una ficha de una posición a otra. ===== Resolución ===== En primer lugar, voy a suponer un tablero cuadrado y una pieza que ocupa un solo lugar, por lo que sus movimientos son arriba, abajo, izquierda y derecha. domains %Un casillero tiene dos coordenadas casillero = casillero(integer, integer) %Una ficha ocupa un casillero ficha = ficha(casillero) lista = ficha* predicates %Mueve una ficha de una posición a otra nondeterm mover(ficha,ficha). %Determina si un casillero esta ocupado nondeterm ocupado(casillero). %Determina si una ficha está en una posición válida valida(ficha). %Determina si un casillero pertenece al tablero adentro(casillero). %Hace un recorrido en profundidad %pp(estado de inicio, estado final, limite de profundidad, lista de estados de la solucion, lista de estados ya recorridos nondeterm pp(ficha,ficha,integer,lista,lista) %Determina si un estado pertenece a una lista de estados nondeterm pertenece(ficha,lista) %Determina el desplazamiento permitido nondeterm delta(integer) %Determina el tamaño del tablero tamanio(integer) clauses %Base de conocimientos global sobre los obstaculos del tablero. (ejemplos de obstáculos) ocupado(casillero(2,2)). ocupado(casillero(3,2)). ocupado(casillero(4,2)). ocupado(casillero(2,3)). ocupado(casillero(4,3)). %Una ficha esta en una posicion valida si esta en casilleros libres y dentro del tablero valida(ficha(casillero(X1,Y1))):-not(ocupado(casillero(X1,Y1))),adentro(casillero(X1,Y1)). %Un casillero pertenece al tablero si sus dos coordenadas pertenecen adentro(casillero(X,Y)):- tamanio(Max), X>0, X<=Max, Y>0, Y<=Max. %El desplazamiento puede ser positivo o negativo delta(-1). delta(1). %El tablero es de 5 casillas por 5 casillas tamanio(5). %%%%%%%%%%%%%%%%%%%% %Reglas del proceso% %%%%%%%%%%%%%%%%%%%% %Muevo la pieza a izquierda o a derecha mover(ficha(casillero(X1,Y1)),ficha(casillero(X2,Y1))):- delta(D), X2 = X1 + D, valida(ficha(casillero(X2,Y1))). %Muevo la pieza para arriba o para abajo mover(ficha(casillero(X1,Y1)),ficha(casillero(X1,Y2))):- delta(D),Y2 = Y1 + D, valida(ficha(casillero(X1,Y2))). %El recorrido en profundidad termina si el estado inicial es igual al final pp(E,E,_,[E],_):-!. %O se agrega un nuevo estado a los visitados, y se vuelve a probar pp(EI, EF, N,[EI|R], Visitados):- N > 0, N1 = N-1, mover(EI, E2), not(pertenece(E2, Visitados)), pp(E2, EF, N1, R, [E2|Visitados]),!. %El estado pertenece a la lista, si es igual a la cabeza pertenece(X,[X|_]). %O si pertenece a la cola pertenece(X,[_|T]) :- pertenece(X,T),!. Goal Inicial = ficha(casillero(1,1)), Final = ficha(casillero(3,3)), pp(Inicial, Final, 20, L, [Inicial]). A continuación, otra solución para el caso en que la ficha debe ocupar dos casilleros, por lo que se agregan los movimientos de rotación domains %Un casillero tiene dos coordenadas casillero = casillero(integer, integer) %La pieza puede estar horizontal o vertical orientacion = symbol %Una ficha ocupa dos casilleros ficha = ficha(casillero, orientacion) lista = ficha* predicates %Mueve una ficha de una posición a otra nondeterm mover(ficha,ficha). %Determina si un casillero esta ocupado nondeterm ocupado(casillero). %Determina si una ficha está en una posición válida valida(ficha). %Determina si un casillero pertenece al tablero adentro(casillero). %Hace un recorrido en profundidad %pp(estado de inicio, estado final, limite de profundidad, lista de estados de la solucion, lista de estados ya recorridos nondeterm pp(ficha,ficha,integer,lista,lista) %Determina si un estado pertenece a una lista de estados nondeterm pertenece(ficha,lista) %Determina el desplazamiento permitido nondeterm delta(integer) %Determina el tamaño del tablero tamanio(integer) clauses %Base de conocimientos global sobre los obstaculos del tablero/ ocupado(casillero(2,2)). ocupado(casillero(3,2)). ocupado(casillero(4,2)). ocupado(casillero(2,3)). ocupado(casillero(4,3)). %Una ficha esta en una posicion valida si esta en casilleros libres y dentro del tablero valida(ficha(casillero(X,Y),horizontal)):-not(ocupado(casillero(X,Y))),X2 = X + 1,not(ocupado(casillero(X2,Y))),adentro(casillero(X,Y)),adentro(casillero(X2,Y)). valida(ficha(casillero(X,Y),vertical)):-not(ocupado(casillero(X,Y))),Y2 = Y + 1,not(ocupado(casillero(X,Y2))),adentro(casillero(X,Y)),adentro(casillero(X,Y2)). %Un casillero pertenece al tablero si sus dos coordenadas pertenecen adentro(casillero(X,Y)):-X>0, X<=5, Y>0, Y<=5. %El desplazamiento puede ser positivo o negativo delta(-1). delta(1). %El tablero es de 5 casillas por 5 casillas tamanio(5). %%%%%%%%%%%%%%%%%%%% %Reglas del proceso% %%%%%%%%%%%%%%%%%%%% %Muevo la pieza a izquierda o derecha mover(ficha(casillero(X1,Y),Pos),ficha(casillero(X2,Y),Pos)):- delta(D),X2 = X1 + D, valida(ficha(casillero(X2,Y),Pos)). %Muevo la pieza para arriba o para abajo mover(ficha(casillero(X,Y1),Pos),ficha(casillero(X,Y2),Pos)):- delta(D),Y2 = Y1 + D, valida(ficha(casillero(X,Y2),Pos)). %Roto la pieza de | a _ mover(ficha(casillero(X,Y),vertical),ficha(casillero(X,Y),horizontal)):- valida(ficha(casillero(X,Y),horizontal)). mover(ficha(casillero(X,Y),vertical),ficha(casillero(X1,Y),horizontal)):- X1 = X - 1, valida(ficha(casillero(X1,Y),horizontal)). %Roto la pieza de _ a | mover(ficha(casillero(X,Y),horizontal),ficha(casillero(X,Y),vertical)):- valida(ficha(casillero(X,Y),vertical)). mover(ficha(casillero(X,Y),horizontal),ficha(casillero(X,Y1),vertical)):- Y1 = Y + 1, valida(ficha(casillero(X,Y1),vertical)). %El recorrido en profundidad termina si el estado inicial es igual al final pp(E,E,_,[E],_):-!. %O se agrega un nuevo estado a los visitados, y se vuelve a probar pp(EI, EF, N,[EI|R], Visitados):- N > 0, N1 = N-1, mover(EI, E2), not(pertenece(E2, Visitados)), pp(E2, EF, N1, R, [E2|Visitados]),!. %El estado pertenece a la lista, si es igual a la cabeza pertenece(X,[X|_]). %Dos piezas también son iguales aunque estén expresadas con las coordenadas al revés %pertenece(ficha(casillero(X1,Y1),casillero(Y2,X2)),[ficha(casillero(X2,Y2),casillero(X1,Y1))|_]). %O si pertenece a la cola pertenece(X,[_|T]) :- pertenece(X,T),!. Goal Inicial = ficha(casillero(1,1),horizontal),Final = ficha(casillero(3,3),vertical),pp(Inicial, Final, 20, L, [Inicial]). ===== Discusión ===== Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá.