Análise de Métodos Eficientes para Solução do Cubo Mágico

Aluno: Walter Pereira Rodrigues de Souza
Supervisora: Nina S. T. Hirata


* Resumo da monografia

  Desde sua popularização no início da década de 1980, o cubo mágico,
quebra-cabeça inventado pelo arquiteto húngaro Ernö Rubik, é objeto de estudo
tanto da matemática quanto da computação.

  Atualmente há bastante literatura tratando da formalização do quebra-cabeça
(usando Teoria dos Grupos) ou de algoritmos de busca para soluções ótimas, mas
pouco se fala sobre métodos que levam a soluções não-ótimas. Este trabalho tem
como objetivo preencher essa lacuna.


* Objetivos

  O objetivo deste trabalho é comparar a eficiência dos métodos mais populares
de resolução de cubo mágico.

  Para cada método, um programa será desenvolvido para enumerar e resolver
otimamente os estados válidos dentro de cada passo. Dessa forma encontraremos um
limite superior para o número de movimentos necessários para a resolução e
também teremos uma lista de "algoritmos" necessários para a execução.


* Atividades já realizadas

  Todos os métodos que serão analisados são de meu conhecimento.

  Até o momento, programas que implementam os seguintes métodos já foram
desenvolvidos: Kociemba, Fridrich (primeiro, terceiro e quarto passos), Pochmann
(quinas e meios) e M2.


* Estrutura da monografia

  - Introdução
  
  - Nomenclatura e notação
  
  - Métodos para computadores
    - Thistlewait
    - Kociemba
  
  - Métodos para humanos
    - Camada por camada
    - Fridrich
    - Petrus
    - Roux
    - ZZ
    - Waterman
    - MGLS
    - ZB
  
  - Métodos para resolução vendada
    - Quinas
      - Pochmann
      - 3OP
      - R2
      - Beyer-Hardwick
    - Meios
      - Pochmann
      - 3OP
      - M2
      - Beyer-Hardwick

  - Conclusões

  - Bibliografia


  Além dos itens acima, haverá uma seção descrevendo experiências pessoais
adquiridas durante o desenvolvimento do trabalho.


* Cronograma de trabalho

  junho: métodos para humanos
  julho: métodos para computador e para resolução vendada
  agosto e setembro: monografia e pôster