Descrição do Problema

O jogo dos 15 é representado por uma matriz 4x4 onde há 15 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.

Nota: Para alguns conjuntos de configurações iniciais e finais, este problema, assim como a sua versão reduzida - jogo dos oito, não tem solução. Investigue sobre este assunto e implemente no seu programa, um código que verifique se, para uma dada configuração inicial do jogo dos 15, há um caminho que leve à solução final, SEM fazer nenhuma busca. (Na página da disciplina http://www.dcc.fc.up.pt/~ines/aulas/1718/IA/IA.html, poderá encontrar alguns links relevantes sobre a dualidade de problemas deste tipo e dicas de como economizar memória).