Usei Python e uma primeira pesquisa em largura de 2 lados para resolver um cubo de Rubiks 2x2.
Inspirado no projeto do MIT 6.006. Criado do zero com exclusividade.
https://youtu.be/ZHxLO6fubaU
Criou a API, o algoritmo e a GUI do cubo do zero. Cada um dos 6 lados possui 4 quadrados diferentes, resultando em 24 quadrados. Além disso, há um total de 8 peças de canto que compõem o cubo, cada uma das quais tem 3 orientações e, portanto, acompanha os 24 quadrados.
Eu defini cada uma das 24 subseções de cada lado como uma string com 'xyz' como o formato onde x é a cor imediatamente voltada e y e z vão no sentido horário ao redor do cubo para aquele canto.
Contornei o cubo e atribuí a cada lado um número fixo representando o estado resolvido. Por exemplo, 0, 1, 2, 3 são as 4 partes da frente voltada para o lado branco, onde 0 está no canto superior esquerdo e o outro segue no sentido horário.
Existem 12 movimentos que podem ser realizados no cubo. Direita, esquerda, superior, inferior, frontal, traseira. Cada um deles também tem movimentos no sentido anti-horário, então 6x2 = 12 movimentos. Cada um desses 12 manipula metade do cubo, formando 12 quadrados. Para fazer esses movimentos, criei dicionários para cada um dos 6 no sentido horário para os quais o subquadrado gira do original para a posição seguinte. Para fazer os números primos, apenas troquei as chaves e os valores.
Resolver este problema é especialmente complicado devido à enorme quantidade de permutações possíveis do cubo. Existem 24 subquadrados e isso resulta em 24P24 = 24!. Isso é da magnitude de 10 ^ 23. São menos que esse valor devido a determinadas situações, mas o número ainda é enorme.
Para criar a árvore, eu teria que executar cada um dos movimentos e executar todos os movimentos dos movimentos, o que fica muito grande. 12^altura da árvore. Consegui limitar esse tamanho criando um ditado de posições visitadas para não refazer a ação para permutações visitadas anteriormente.
Comecei criando um BFS unilateral, mas isso atingiria o limite de recursão, pois a árvore ramificada ficaria muito grande. Para corrigir isso, usei um BFS de 2 lados alternando a criação de ramificações do início e da solução final. Iria criar as árvores e verificar se o lado oposto já havia encontrado o ponto. Se assim fosse, retornaria o ponto de conexão.
Durante tudo isso, cada nó salva seu pai (para a ramificação frontal) ou filho (para a ramificação posterior). Para encontrar a rota seguida, encontrei recursivamente o pai do nó de conexão e, em seguida, todos os filhos daquele ponto. Isso resultou em uma série de posições que foram tomadas, desde as embaralhadas até as resolvidas.
Este projeto aplicou meu uso da teoria dos grafos e da pesquisa em amplitude . Melhorei minha habilidade em Python e recursão. Eu também descobri experimentalmente que os movimentos máximos para resolver um cubo 2x2 são 11 movimentos, já que nunca consegui encontrar uma solução que demorasse mais
Aprendeu como usar a biblioteca tkinter para fazer GUI para o projeto
