Primeiro Trabalho de IA/SI
Estimativa de término: 14/03/2016
24 de Fevereiro de 2016

Este trabalho não é para ser entregue nem apresentado. Será desenvolvido principalmente durante as aulas práticas, mas espera-se que o estudante complemente as horas de contato com trabalho extra-classe. Os testes e exames terão perguntas relacionadas com este trabalho. Para saber o método e critério de avaliação, por favor consulte a ficha da unidade curricular na página do sigarra.

O jogo dos 8 é representado por uma matriz 3x3 onde há 8 células numeradas e uma célula em branco. Variações deste jogo podem conter parte de uma imagem em cada célula. O problema consiste em partir de uma configuração inicial embaralhada das células e chegar a uma configuração final com uma ordenação determinada de algarismos (no caso da matriz de números) ou de imagens (no caso da matriz onde as células representam partes de uma imagem). Os movimentos/operadores possíveis para se chegar de uma configuração a outra são: 1) mover a célula em branco para cima, 2) mover a célula em branco para baixo, 3) mover a célula em branco para a direita e 4) mover a célula em branco para a esquerda.

Dada a descrição do problema acima, implemente uma solução usando:

A implementação pode ser em qualquer linguagem.

Para cada estratégia, analise:

Utilize as seguintes configurações iniciais:

3 4 2   6 2 7
5 1 7   5   3
6   8   8 1 4
             

A primeira configuração tem solução ótima em profundidade 23 (menor nmero de movimentos possível para chegar da configuração inicial à configuração final).

A segunda configuração inicial não leva à configuração final proposta. Explique o porque.

Apesar de propor apenas uma configuração inicial e final para teste, prepare o seu programa de forma a ser possível entrar com diversas configurações iniciais e finais. Portanto, escreva o seu código de forma que o utilizador possa escolher as configurações inicial e final. O seu código deve verificar se há solução para chegar do estado inicial ao estado final antes de iniciar a busca, e deve emitir uma mensagem de erro se não houver caminho entre a solução inicial e a final.

A configuração final de teste deve ser a seguinte:

1 2 3
8   4
7 6 5

Utilize o algoritmo 1 como base para implementar todas as buscas:


\begin{algorithm}
% latex2html id marker 42
[hbtb]
\caption{Algoritmo Geral de ...
...
\EndWhile
\State return \lq\lq solution not found''
\end{algorithmic}\end{algorithm}

Este algoritmo recebe como parâmetro uma função de enfileiramento que será utilizada para ordenar a lista de nós (configurações) abertos (ainda não explorados).



InĂªs Dutra 2016-02-24