Guião para a Décima Primeira Aula Prática de IPL

Delfim F. Marado Torres

25 de Maio de 1999

Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.

1 Objectivos da aula

São objectivos da aula:

Resolver o problema das oito rainhas.
Implementar, usando uma gramática (DCG), um interface em língua natural que permita interagir (acrescentar e consultar informação) com uma base de conhecimento (BC) com predicados profissao/2 e curso/2.

2 O problema das 8 rainhas

2.1 Enunciado e estratégia de resolução

O problema das 8 rainhas é um problema bem conhecido, muitas vezes usado para introduzir a ideia de retrocesso (backtracking). Consiste em colocar 8 rainhas num tabuleiro de xadrez (8 ×8) de tal modo que nenhuma rainha ataque outra. A abordagem habitual, para resolver este problema, consiste numa pesquisa exaustiva de todas as possibilidades de colocação das rainhas. Numerando as linhas e as colunas de 1 a 8, então cada uma dessas possibilidades pode ser representada por um óctuplo

[ [1,c₁], ¼, [8,c₈] ],

onde [i,c_i] denota a posição de uma rainha no quadrado da linha i e coluna c_i. Podemos representar esta configuracão apenas por

[ c₁, ¼, c₈ ],

convencionando que a i-esima posição denota, implicitamente, a linha i. Além disso, como duas rainhas na mesma coluna atacam-se mutuamente, apenas precisamos de considerar os óctuplos [ c₁, ¼, c₈ ] que sejam uma permutacão de [1, 2, 3, 4, 5, 6, 7, 8]. Para resolver este problema temos então, essencialmente, de:

achar uma permutação de [1, 2, 3, 4, 5, 6, 7, 8];
verificar se essa permutação é uma solução.

2.2 Uma solução

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         % Problema das 8 rainhas
         % Delfim F. Marado Torres, 24/Maio/1999
         %
         % No livro do Bratko, pp. 108--118,
         % pode encontrar outras resolucoes
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         % Predicado principal: rainhas(Solucao)
         %
         % Solucao sera' instanciada com uma
         % lista da forma [ [1,Y1], ..., [8,Y8] ]
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         rainhas(S) :-
           permutacao([1,2,3,4,5,6,7,8],P),
           formaPares(P,S),
           naoAtaca(S).

         formaPares(L,LP) :-
           fp(1,L,LP).

         fp(_,[],[]).
         fp(N,[X|R],[[N,X]|RP]) :-
           N1 is N + 1,
           fp(N1,R,RP).

         naoAtaca([]).
         naoAtaca([P|RP]) :-
           naoAtacaNenhuma(P,RP),
           naoAtaca(RP).

         naoAtacaNenhuma(_,[]).
         naoAtacaNenhuma([X,Y],[[X1,Y1]|RP]) :-
           not emLinha([X,Y],[X1,Y1]),
           naoAtacaNenhuma([X,Y],RP).

         emLinha([X,_],[X,_]).
         emLinha([_,Y],[_,Y]).
         emLinha([X1,Y1],[X2,Y2]) :-
           D is abs(Y2 - Y1),
           D is abs(X2 - X1).

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% Predicados ja realizados anteriormente
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         permutacao([],[]).
         permutacao([X|R],P) :-
           permutacao(R,RP),
           adiciona(X,RP,P).

         adiciona(X,R,[X|R]).
         adiciona(X,[Y|R],[Y|A]) :-
           adiciona(X,R,A).

2.3 Uma curiosidade

Sabe quantas soluções diferentes existem para o problema das 8 rainhas? Nada mais nada menos que 92! Tal como eu, pode descobrir isso com o comando

         ?- tell('rainhas.txt'), rainhas(S), write(S), nl, fail.

         No
         told.   % escrevi eu

         Yes
         ?-

dando depois uma vista de olhos ao ficheiro rainhas.txt.

3 Gramática 'BC'

3.1 O pretendido

Pretende-se construir, e posteriormente consultar, uma Base de Conhecimento em Prolog com predicados profissao/2 e curso/2

         profissao(Pessoa,Actividade).
         curso(Pessoa,Curso).

através de um interface que use a língua portuguesa. Eis alguns exemplos do funcionamento pretendido:

Se dissermos ``O xico é fotógrafo.'', então será acrescentado (automaticamente, por meio de um assertz) à BC o facto
```
         profissao(xico,fotografo).
```
Se afirmarmos ``A zé estuda matemática.'', então será acrescentado à BC o facto
```
         curso(ze,matematica).
```
Se, depois das afirmações anteriores, perguntarmos ``O que faz o xico?'', obteremos como resposta ``xico é fotógrafo.''.
Se perguntarmos ``O que faz a zé?'', obteremos como resposta ``zé estuda matemática.''.

Para o sistema Prolog reconhecer as frases acima e fazer, sozinho, as respectivas acções (acrescentar ou consultar conhecimento) vamos recorrer a uma DCG.

3.2 Uma solução

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Gramatica 'BC'
%%
%% Delfim F. Marado Torres
%% 25/Maio/1999
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

gramBC -->
  afirmacao(Tipo,Pess,Act),
  { acrescentaBC(Tipo,Pess,Act) }.
gramBC -->
  questao(Pess),
  { daActividade(Pess) }.

afirmacao(profissao,P,A) -->
  det(_),
  [P, e, A, '.'].
afirmacao(curso,P,A) -->
  det(_),
  [P, estuda, A, '.'].

questao(Pess) -->
  det(masculino),
  [que, faz],
  det(_),
  [Pess, '?'].

det(masculino) --> [o] | ['O'].
det(feminino) -->  [a] | ['A'].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Accoes Semanticas da Gramatica
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

acrescentaBC(Tipo,Pess,Act) :-
  C =..[Tipo,Pess,Act],
  assertz(C),
  write('A clausula '),
  write(C),
  write(' foi adicionada com sucesso.'),
  nl.

daActividade(P) :-
  profissao(P,A),
  informa(' e ',P,A).
daActividade(P) :-
  curso(P,A),
  informa(' estuda ',P,A).
daActividade(P) :-
  write(P),
  write(' nao consta da BC!'),
  nl.

informa(T,P,A) :-
  write(P),
  write(T),
  write(A),
  write('.'),
  nl.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Predicado Principal: bc/1
%%
%% Recebe uma string em vez de uma lista
%%
%% EXEMPLOS:
%%
%% ?- bc('O xico e fotografo.').
%% A clausula profissao(xico,fotografo) foi adicionada com sucesso.
%%
%% ?- bc('A ze estuda matematica.').
%% A clausula curso(ze,matematica) foi adicionada com sucesso.
%%
%% ?- bc('O que faz o xico?').
%% xico e fotografo.
%% ?- bc('O que faz a ze?').
%% ze estuda matematica.
%%
%% ?- bc('O que faz o delfim?').
%% delfim  nao consta da BC!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

bc(String) :-
  converte(String,Lista),!,
  gramBC(Lista,[]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Predicado ja' usado na teorica.
%%
%% Transforma uma string numa lista de palavras.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

converte(S,L) :-
  name(S,LA1),
  adicionaEspacos(LA1,LA2),
  conv(LA2,L).

adicionaEspacos([],[]).
adicionaEspacos([X|R1],[32,X,32|R2]) :-
  member(X,[58,59,44,46,33,63]),
  adicionaEspacos(R1,R2).
adicionaEspacos([X|R1],[X|R2]) :-
  adicionaEspacos(R1,R2).

conv([],[]).
conv(LA,[P|R]) :-
  palavra(LA,PA,RA),
  name(P,PA),
  conv(RA,R).

palavra([],[],[]).
palavra([32|R],[],L) :-
  desprezaEspacos(R,L).
palavra([X|R1],[X|R2],L) :-
  palavra(R1,R2,L).

desprezaEspacos([32|R1],R) :-
  desprezaEspacos(R1,R).
desprezaEspacos(L,L).