5200 Paradigma de Programação Lógico e Funcional

Trabalho / Resolvedor do jogo TetraVex em Prolog

Introdução

O objetivo deste trabalho é a implementação de um resolvedor do jogo TetraVex em Prolog.

O trabalho é em equipe de até duas pessoas. O compartilhamento de informações entre as equipes é permitido (e aconselhado), mas o compartilhamento de código não é permitido. Trabalhos que tenham porções significativas de código iguais, ou copiados da internet, serão anulados. Veja a resolução Nº 008/2007-COU para as possíveis sansões disciplinares. Cada membro da equipe deverá apresentar o trabalho individualmente para o professor.

Descrição

TetraVex é um jogo de quebra-cabeça de correspondência de borda. É dado uma grade de blocos, cada bloco com um número em cada borda. O objetivo é colocar cada bloco em uma posição apropriada. Um bloco está em uma posição apropriada se os blocos adjacentes (acima, a direita, abaixo e a esquerda) tem o mesmo valor nas bordas adjacentes. Por exemplo, a figura abaixo mostra um jogo inicial com 3 linhas e 3 colunas

O jogador deve organizar os blocos de maneira que eles fiquem em posições apropriadas, como por exemplo

Este trabalho consiste na implementação de um resolvedor para o jogo TetraVex em Prolog.

É dado uma implementação inicial (ingênua) do predicado principal. Esta implementação testa todas as possíveis permutações dos blocos de entrada. Ela não é adequada (é muito lenta) para jogos com mais do que 9 blocos.

O principal desafio deste trabalho é implementar um método mais eficiente. A implementação inicial é ruim porque testa uma solução completa para verificar a sua validade. Um método mais eficiente deve verificar a validade da solução conforme ela vai sendo construída.

Um possibilidade consiste em escolher um bloco válido para a primeira posição, depois escolher um bloco válido para a segunda posição, etc, até que todos as posições tenham sido preenchidas. Se em algum momento não houver mais escolhas válidas para uma determinada posição, o processo deve retroceder (backtrack) e tentar outra alternativa para a posição anterior.

Você pode escolher implementar outra estratégia, mas ela deve ser eficiente (passar no teste tetravex_grande em menos de 1 minuto).

Você pode ganhar 1,0 ponto extra na nota do trabalho se a sua implementação passar no teste tetravex:desafio em menos de 1 minuto.

Desenvolvimento

Para facilitar o desenvolvimento do programa, está disponível um “projeto” com os arquivos iniciais de código e um Makefile para testar e enviar o programa.

Para fazer o download do projeto é necessário ter o git instalado. No Ubuntu ou Debian o git pode ser instalado com o comando apt-get install git.

Para fazer o download do projeto, execute o comando

git clone http://malbarbo.pro.br/git/tetravex-prolog

Após a execução deste comando, um diretório chamado tetravex-prolog terá sido criado.

Você deve escrever o código do programa no arquivo src/prolog/tetravex.pl e os testes no arquivo src/prolog/testes.pl.

Execução dos testes

Os testes estão no arquivo src/prolog/testes.pl. Execute todos os testes com o comando

make testar

Veja as instruções para executar testes individuais no arquivo src/prolog/testes.pl.

Envio do trabalho

Para enviar o trabalho, execute o comando

make enviar

O script de envio criará um arquivo compactado com os arquivos a serem entregues para correção e enviará para a página do professor.

Após enviar o trabalho, o aluno deverá entrar na página da disciplina, imprimir e assinar o termo de autoria. O termo de autoria é um documento em que o aluno afirma que ele é o autor do código do trabalho que ele enviou e que portanto, não copiou parte significativa do programa de outra pessoa ou da internet.

Avaliação

O trabalho será avaliado de acordo com os critérios:

• Clareza lógica: a lógica nos programas deve ser clara.
• Corretude e completude: o programa tem quer passar em todos os testes e todos os predicados não triviais devem ter testes.
• Tempo: o programa deve passar no teste testravex_grande em menos de 1 minuto.
• Boas práticas de programação: o código deve estar bem escrito e organizado; os recursos da linguagem devem ser usados corretamente.

Dicas

Esta seção contém algumas dicas de implementação. Use as que achar útil.

• Antes de implementar o programa em Prolog, resolva as listas de exercícios. Você terá muitas dificuldades em implementar o trabalho se você nunca resolveu alguns problemas em Prolog antes.