A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos

• Ano de defesa: 2024
• Autor(a) principal: Martins, Lia Alessandra da Silva
• Outros Autores: http://lattes.cnpq.br/1657347391123253
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Instituto de Computação; Brasil; UFAM; Programa de Pós-graduação em Informática
• Palavras-chave em Português: CIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAO; Algoritmos; Caminhos; Complexidade computacional; Jogos combinatórios; Teoria dos grafos; Torre de Hanoi
• Link de acesso: https://tede.ufam.edu.br/handle/tede/10521

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.