Como começou

Meu filho adora cubos. Ele já resolveu um cubo 8×8 e até um cubo que dizem ser o mais difícil do mundo. Eu também tentei aprender pelo menos o 3×3, mas travei na 8ª etapa do método e nunca entendi bem os princípios.

Então decidi criar um programa que monta o cubo na tela, lê um cubo de verdade a partir de fotos e mostra a solução uma jogada por vez.

O cubo 3D

  • Ele é desenhado com Qt6 e OpenGL. Arrastando com o mouse, o cubo inteiro gira; clicando com o botão esquerdo em uma casa, aquela fileira gira para a esquerda ou para a direita, e com o botão direito, para cima ou para baixo.
  • No começo, clicando na mesma casa, às vezes girava para o lado certo e às vezes para o lado oposto. Quando o cubo estava inclinado, ele confundia a face da frente com a face lateral. Corrigimos depois de testar todas as direções com um simulador de direção de giro (simulate_moves).
  • Por causa da iluminação e das sombras, o branco parecia cinza e a face de baixo parecia preta, então tiramos os efeitos de iluminação.

Duas fotos dão as 54 casas

Fotografando o cubo por um canto, aparecem três faces em uma foto. Tirando mais uma foto do canto oposto, aparecem as seis faces.

  1. Foto 1: com o amarelo para cima, mostrando cima, frente e direita
  2. Foto 2: virado com o branco para cima, mostrando baixo, trás e esquerda

A casa central de cada face não se move quando o cubo é girado. Por isso, a cor do centro define qual face é. O esquema de cores é amarelo em cima, branco embaixo, verde na frente, laranja à direita, vermelho à esquerda e azul atrás.

Verificação de regras

Se uma foto for lida errado, o resultado pode ser um cubo que na prática não poderia ser montado. Por isso, quando chega a planificação, verificamos as regras primeiro.

  • Os 6 centros precisam ter suas cores fixas.
  • Cada uma das 8 peças de canto precisa ter três cores diferentes, e cores opostas (amarelo e branco, verde e azul, vermelho e laranja) não podem aparecer na mesma peça.
  • As 12 peças de aresta são verificadas do mesmo jeito, e a mesma peça não pode aparecer duas vezes.

As casas que falham são marcadas com uma borda vermelha. Ao clicar em uma delas, aparece um anel com as seis cores em volta para corrigi-la na hora.

Esta é a tela inicial depois de ler uma foto do cubo lançado na Coreia. As bordas vermelhas são as casas que falharam nas regras.

Resolução

Quando as regras passam, a solução é encontrada com a busca em duas fases de Kociemba. Não é um método que as pessoas decoram, e sim um algoritmo que usa tabelas pré-calculadas para encontrar soluções curtas. Ele resolveu todos os 60 cubos embaralhados com 25 jogadas, com média de 20,7 jogadas e no máximo 22. O tempo mediano por resolução foi de 6 ms. Os botões ◀ Anterior / Próximo ▶ na parte de baixo da tela avançam uma jogada por vez.

Também fizemos um resolvedor para iniciantes, camada por camada, mais próximo de como as pessoas resolvem. Mas ele resolveu só 6 dos mesmos 60 (10%), e os que resolveu levaram de 203 a 311 jogadas. Por isso o app usa primeiro o Kociemba e só passa para outros métodos quando ele falha.

O gráfico de tempo usa escala logarítmica.

O código real desta etapa

Esta é a verificação das peças de canto. Se alguma das três cores se repetir, as três casas são marcadas.

src/CubePhotoReconstructor.cppcpp · 25 linhas
// 2) 코너 (8개): 세 면 색은 모두 달라야 하고, 서로 다른 축 색이어야 함
for (int x : {-1, 1}) {
    for (int y : {-1, 1}) {
        for (int z : {-1, 1}) {
            const int fx = (x == 1) ? 0 : 1;
            const int fy = (y == 1) ? 2 : 3;
            const int fz = (z == 1) ? 4 : 5;
            const int cx = colorOnFace(faces, fx, x, y, z);
            const int cy = colorOnFace(faces, fy, x, y, z);
            const int cz = colorOnFace(faces, fz, x, y, z);
            if (cx < 0 || cy < 0 || cz < 0)
                continue;

            if (cx == cy || cy == cz || cx == cz) {
                v.ok = false;
                v.errors << QStringLiteral(
                                "· %1+%2+%3 모서리: 한 조각에 같은 색이 두 면 — "
                                "전개도에서 이 세 칸이 「왼|앞|오른」 접힘에 맞게 붙어 있는지 확인")
                                .arg(QString::fromUtf8(CubeModel::faceNameKo(fx)),
                                     QString::fromUtf8(CubeModel::faceNameKo(fy)),
                                     QString::fromUtf8(CubeModel::faceNameKo(fz)));
                markCell(v, fx, x, y, z);
                markCell(v, fy, x, y, z);
                markCell(v, fz, x, y, z);
            }

A resolução chama o Kociemba primeiro.

src/Oracle.cppcpp · 6 linhas
// 0) Kociemba two-phase — 임의 스크램블/사진 상태용 확실한 해법
if (!timedOut()) {
    auto koc = KociembaSolver::solve(start, 24, 8);
    if (!koc.empty())
        return compress(koc);
}

O próximo post é "2. Segmentação de cores em vez de um VLM, e dois cubos com personalidades diferentes".