Universidade de São Paulo
Instituto de Ciências Matemáticas e de Computação
Departamento de Ciências da Computação e Estatística
Primeiro Semestre de 1999

SCE 5774 - Introdução à Inteligência Artificial

                  Profa.: Sandra Maria Aluísio
                        e-mail: sandra@icmsc.sc.usp.br

                  Aluno: Pastor W. Gonzales Taco
                        e-mail: pastor@sc.usp.br

 

Primeiro Projeto: Crypto-arithmetic Puzzles

 

1. Enunciado do Problema

2. Estrutura do Programa em Prolog

3. Características Necessárias para Resolução

4. Teste do Programa

5. Conclusões

 

 

1. Enunciado do Problema

 

Crypto-arithmetic Puzzles. Implemente um resolvedor genérico de puzzles aritméticos como o clássico:

**   SEND
** +MORE
** -------
** MONEY

O objetivo deste jogo é atribuir um digito a cada letra em SEND e MORE e então adicionar aqueles valores como um problema matemático normal e obter MONEY como resposta. Faça um programa genérico, com a restrição de que 2 números para ser adicionados tenham o mesmo número de digitos e a solução um digito a mais (veja que send e more tem 4 digitos e money 5). Outra entrada:

                          [C,R,O,S,S] + [R,O,A,D,S] = [D,A,N,G,E,R].
 

 

2. Estrutura do Programa em Prolog

 

    main:-
             write($Puzzle? $),
             read(Puzzle),
             solve(Puzzle),
             write(Puzzle),nl,
             fail.
    main:- write($no more$),nl.

    solve([A|At] + [B|Bt] = [C0,C|Ct]) :-
             permutation([A,B,C0,C], [0,1,2,3,4,5,6,7,8,9],L),
             A \= 0, B \= 0, C0 \= 0,
             (X = 0; X = 1),
             A + B + X =:= 10 * C0 + C,
             solve2(At+Bt=Ct,X,L).

    solve2([A] + [B] = [C], X, L) :-
             permutation([A,B,C],L,_),
             (X = 0, A + B =:= C; X = 1, A + B =:= 10 + C).
    solve2([A|At] + [B|Bt] = [C|Ct], X, L) :-
             permutation([A,B,C],L,L1),
             (X1 = 0; X1 = 1),
             (X = 0, A + B + X1 =:= C; X = 1, A + B + X1 =:= 10 + C),
             solve2(At + Bt = Ct, X1,L1).

    permutation([],L,L).
    permutation([A|X],Y,L) :- atomic(A), permutation(X,Y,L).
    permutation([A|X],Y,L) :- remove(A,Y,Y1), permutation(X,Y1,L).

    remove(A,[A|X],X).
    remove(A,[B|X],[B|Y]) :- remove(A,X,Y).
 

 

3. Características Necessárias para Resolução

 

Em uma variedade de problemas de inteligência artificial, determinados valores podem ser asinados a um número de variaveis sujeitas a certas restrições. Uma abordagem comum para resolver esses problemas é atravez da geração e teste de valores. Este proceso consiste em escolhendo algums valores para cada variável, e testando-os para determinar se a combinação de tais valores satisfaz as restrições. De ser assim o problema é resolvido, se não, escolhe-se um novo conjunto de valores os quais são asignados as variáveis, para provar outra vez. Em outras abordagems procura-se a geração, teste e permutação de valores. Antes de passar a ver como funciona o programa, primeiro veremos a seguir alguns aspectos relacionados com os predicados e termos usados do Prolog no programa.

 

Entrada e Saida:

read(X) Este predicado destina-se à leitura de termos do teclado.Todo o termo escrito deve terminar com um ponto ( . ). Este termo podeser uma palavra isolada, uma lista de letras ou ainda um string de caracteres. No caso do programa perante o predicado write($Puzzle? $) ao escrever a sintaxe do Puzzle, o sistema encarará o Puzzle como um argumento associado à variável X.

write(X) Imprime termos associados a X. São válidas as mesmasobservações feitas para read.

nl Provoca a quebra da linha, sendo que o próximo comando deimpressão iniciará numa nova linha.

No programa podemos ver estes predicados de entrada e saida

             write($Puzzle? $),
             read(Puzzle),
             solve(Puzzle),
             write(Puzzle),nl,

remove(A,[B|X],[B|Y]) :- remove(A,X,Y).

Onde o símbolo :- indica a uma condição (se) ou, no caso de compararmos com lógica de predicados, a uma implicação material. A regra é o instrumento básico de organizaçãodo banco de conhecimentos e permite a construção de questõescomplexas (formas mais sofisticadas de consulta ao banco de dados). É ela que indica a validade de um conjunto de fatos, questões ou conjunções. Percebemos, então, que há a possibilidade de construçãode produções complexas em cada regra, permitindo conceitoscada vez maiores e consultas com um maior nível de definição e de variáveis.

  • Operadores Numéricos:

  • Relacionais: Operadores numéricos relacionais são aqueles usadospara realizar testes quantitativos entre dois números. Alguns dos utilizados (existindo outros) no programa são: = (igual), \= (diferente).

    Aritméticos: Operadores aritméticos são os utilizados na aritmética básica e os utilizados aqui são: + (soma), * (multiplicação).

    A \= 0, B \= 0, C0 \= 0,
    (X = 0; X = 1),
    A + B + X =:= 10 * C0 + C,

    Deste modo, percebemos que há a possibilidade de construçãode diversas funções matemáticas mais complexas a partirde regras e operadores relacionais e aritméticos. De fato existem funções matemáticas mais complexas já implementadas em Prolog.

    solve([A|At] + [B|Bt] = [C0,C|Ct]) :-
                 permutation([A,B,C0,C], [0,1,2,3,4,5,6,7,8,9],L),

    As listas são o principal tipo de estrutura de dados em Prolog, com as quais é possível a construção de vetores e matrizes, com a vantagem de ser uma estrutura de memória dinâmica.

     

    Um resolvedor genérico de Puzzles Aritméticos, como o clássico: SEND + MORE = MONEY, tem como objetivo atribuir um digito a cada letra em SEND e MORE e então somar esses valores como um problema de matemática normal obtendo MONEY como resposta. Expressando o problema na forma de três listas de letras de variáveis ligadas por operadores, pode-se enfrentar a solução do problema, com aplicação de algumas restrições. O puzzle a resolver é um simples termo em Prolog de variáveis com uma mesma letra em comum, tal como o Es em SEND  MORE  MONEY, a qual será restringida para ter o mesmo valor. Os valores que assuman as variáveis serão positivas, e no conjunto de {0,1,2,3,4,5,6,7,8, 9}. A relação definida para as variáveis será preservada por unificação com as listas que compõem as palavras, definidas no programa, sendo que atravesarão varios níveis recursivos para resolver até resolver (solve)o problema.
     

    solve([A|At] + [B|Bt] = [C0,C|Ct])


    O backtracking para o predicado da permutação (permutation) produz números diferentes para serem asignados às variáveis, isso na procura de soluções para o programa. Porém o programa resolverá o problema permutando os valores das letras e aplicando as restrições, se as restrições falham, o programa voltará a permutar até a resposta ser achada.
     

      permutation([A,B,C0,C], [0,1,2,3,4,5,6,7,8,9],L),


    As permutações no programa alocam diferentes valores para as variáveis na primeira lista desde os valores na segunda. A terceira lista é a lista de valores sem serem alocados. Esta trabalha apagando elementos da lista que usa. Assim, apaga o próximo elemento e fixa simplesmente seus valores para a variável, provendo assim um modo simples para nomear e permutar valores para uma lista de variáveis. Ao voltar, as variáveis são apagadas para o próximo elemento da lista, gerando assim eventualmente todas as permutações de uma lista.
     

    permutation([],L,L).
    permutation([A|X],Y,L) :- atomic(A), permutation(X,Y,L).
    permutation([A|X],Y,L) :- remove(A,Y,Y1), permutation(X,Y1,L).

    remove(A,[A|X],X).
    remove(A,[B|X],[B|Y]) :- remove(A,X,Y).

     

    O processso de ressolução torna-se recursivo até chegar à solução, ou soluções do Puzzle.

     

     

    4. Teste do Programa

     

    O programa assim elaborado para ser testado e rodado fazendo uso do software Amzi! 3.3 Prolog. Assim o arquivo puzzle_1.pro contendo o programa, foi compilado e linkado junto ao Amzi! Compiler e Amzi! Linker, respectivamente, como é mostrado a seguir:
     

     


    O programa apresentado (puzzle_1.pro), poderá resolver problemas, com a restrição que os dois números a serem somados tenham o mesmo número de dígitos, e a solução tem um dígito a mais. Nenhum dos primeiros dígitos pode ser zero, podendo o programa ser modificado para ser mais geral.

    A seguir no Amzi! prosseguisse a rodar o programa. Para isso na barra de ferramentas seleccione o comando Listener e logo Star, aparecerá inmediatamente uma janela de consulta. Ir de novo na barra de ferramentas e em Listener seleccionar Consult..., na janela ativa será chamado o arquivo contendo o programa (puzzle_1.pro). Prossiga escrevendo main. e logo o puzzle da forma mostrada na figura a seguir:

     


    Após esse processo deve-se obter os seguinte resultado: [9,5,6,7] + [1,0,8,5] = [1,0,6,5,2]

     

    Pode acontecer problemas na resolução do programa, devido a pouca capacidade na memoria do seu computador. Nesses casos você terá que utilizar Amzi! no "Prompt do MS-DOS", e rodar o programa puzzle_1.pro como pode ser visto a seguir:

     

     

     

     

     

     

    5. Conclusões

     

    O uso de um número limitado de listas, principal tipo de estrutura de dados em Prolog, oferece uma grande vantagem ao permitir uma estrutura de memória dinâmica.

    A asignação de diferentes números para as variáveis é possibilitado pelo processo de backtracking do predicado da permutação (permutation). Esse recurso possibilita a escolha de uma gama diverssa de soluções para o puzzle.

    O processo de permutação é resolvido permutando os valores das letras e aplicando as restrições, se as restrições falham, o programa voltará a permutar até a resposta ser achada. A definição adecuada das restrições poderá facilitar na resolução do puzzle.

    Observa-se que dependendo do tipo de puzzle o número de soluções variará. Assim o processo de recursão nas permutações pode tornar-se insoluvel, ou com várias soluções.

     

     

    Bibliografia: