Examen Final - 75.23. Inteligencia Artificial

Cátedra: Cabrera
Fecha: Primera Oportunidad - Segundo Cuatrimestre 2006
Día: 14/12/2006

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.

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]).