Nesta dissertação é proposto um novo jogo baseado em torres, o Jogo da Torre de Manaus (ToM), sendo uma variação do jogo clássico da Torre de Hanoi (ToH), com restrições nas capacidades dos pinos. Assim, dada uma estrutura com 3 pinos e n discos, o primeiro pino suporta todos os n discos, enquanto o segundo e o terceiro pinos suportam no máximo n-1 e n-2 discos, respectivamente. O objetivo do jogo consiste em, partindo de uma configuração inicial aleatória, mover todos os discos para o primeiro pino respeitando-se tanto as restrições de capacidade quanto as regras do jogo da ToH, de sempre mover um disco por vez e nunca colocar um disco maior em cima de um menor. Dependendo da configuração inicial, o objetivo pode não ser alcançável, o que resulta em um modelo de grafos não conexo. Assim, é dada a caracterização do grafo da ToM, que modela todas as configurações possíveis do jogo como vértices, e as transições válidas entre elas como arestas. São exploradas propriedades desse grafo, como o número de vértices e de componentes conexas. É, também, proposto um algoritmo para solucionar o jogo quando possível, apresentando-se para isto um algoritmo para decidir se o objetivo é alcançável a partir de uma dada configuração ou não. Adicionalmente, é apresentada uma compilação de modelagem em grafos e aspectos algorítmicos das principais variações da ToH encontradas na literatura. Dentre elas, as Torres de Londres e de Oxford, que eram conhecidas apenas como testes neurocognitivos, são formalizadas neste trabalho como jogos combinatórios. Por fim, é proposta uma formalização da construção recursiva do grafo da ToH, usando-se apenas elementos de Teoria dos Grafos, o que ainda não se conhecia na literatura.
|
