Como representar um Cubo de Rubik em uma estrutura de dados

O que há de errado com uma matriz antiga simples de tamanho [6X][X] ? Você não precisa saber sobre mini-cubos internos , porque você não os vê; eles não fazem parte do estado do cubo. Esconda dois métodos feios por trás de uma interface agradável e simples de usar, teste a unidade até a morte e pronto, pronto!

Deve-se notar que eu sou um ávido cuber de velocidade, mas eu nunca tentei programaticamente representar um cubo de Rubik em um algoritmo ou estrutura de dados.

Eu provavelmente criaria estruturas de dados separadas para capturar os aspectos exclusivos de cada bloco em um cubo.

Existem 3 tipos distintos de blocos em um cubo:

1. Corner Block - Tem três faces coloridas e três partes adjacentes com as quais compartilhará um lado a qualquer momento.

2. Edge Block - Tem duas faces coloridas e tem 4 peças adjacentes com as quais compartilhará um lado a qualquer momento. Em blocos 3x3, ele sempre tem 2 peças centrais e 2 peças de canto.

3. Bloco central - Em um cubo 3x3 esta peça não é móvel, mas pode ser girada. Ele sempre terá 4 blocos de borda adjacentes. Em cubos maiores, existem vários blocos centrais que podem compartilhar com outro bloco central ou uma peça de borda. Blocos centrais nunca são adjacentes a um bloco de canto.

Sabendo disso, um bloco pode ter uma lista de referências a outros blocos que ele toca. Eu manteria outra lista de listas, que seria uma lista de blocos que representam uma única face do cubo e uma lista que mantém referências a cada face do cubo.

Cada face do cubo seria representada como uma face única.

Com essas estruturas de dados, seria muito fácil escrever um algoritmo que realiza uma transformação de rotação em cada face, movendo os blocos apropriados para dentro e para fora das listas apropriadas.

EDIT: Nota importante, estas listas devem ser encomendadas, claro, mas esqueci de mencionar isso. Por exemplo, se eu virar o lado direito, o bloco do canto esquerdo do lado direito se moverá para o canto direito do lado direito e será girado no sentido horário.

Quando penso nesse problema, penso em um cubo estático com as cores se movendo em padrões conhecidos. Então ....

Um objeto Cube contém 6 objetos Side que permanecem indexados 0-5. Cada lado contém 9 objetos de posição que permanecem fixos e indexados de 0 a 8. Cada posição contém uma cor.

Para simplificar, manipule todas as ações em incrementos de um quarto de turno. Existem 3 eixos de rotação, cada um em 2 direções possíveis, totalizando 6 ações possíveis no cubo. Com essa informação, torna-se uma tarefa bastante simples mapear as 6 ações possíveis no cubo.

Assim, a cor verde no lado 6, posição 3, pode mover-se para a posição do lado 1 3, ou do lado 2, 7, entre outros, dependendo da ação realizada. Eu não tenho explorado isso o suficiente para encontrar quaisquer traduções matemáticas, mas os padrões provavelmente irão emergir e você pode tirar vantagem do código.

Using the data structure, how can I know if a certain cube in a certain state is solvable? I have been struggling with this question myself and haven't quite found the answer yet.

Para fazer isso, nunca comece com um estado de cubo aleatório. Em vez disso, comece com um estado resolvido e execute as ações n programaticamente para colocar o cubo em um estado inicial aleatório. Como você só tomou medidas legais para chegar ao estado atual, o cubo deve ser solucionável.

Eu encontrei um sistema de coordenadas x-y-z para ser uma maneira simples de endereçar um cubo de Rubik, e matrizes de rotação uma maneira simples e genérica de implementar as rotações.

Eu criei uma classe Piece contendo um vetor de posição (x, y, z) . Uma peça pode ser girada aplicando uma matriz de rotação à sua posição (uma multiplicação matriz vetorial). A peça também mantém faixas de cores em uma tupla (cx, cy, cz) , dando as cores voltadas para cada eixo. Uma pequena quantidade de lógica garante que essas cores sejam atualizadas apropriadamente durante uma rotação: uma rotação de 90 graus no plano X-Y significa que trocaríamos os valores de cx e cy .

Como toda a lógica de rotação é encapsulada na classe Piece, o Cube pode armazenar uma lista não ordenada de Peças, e as rotações podem ser feitas de maneira genérica. Para fazer uma rotação da face esquerda, selecione todas as peças com uma coordenada x de -1 e aplique a matriz de rotação apropriada a cada Peça. Para fazer uma rotação de todo o cubo, aplique a mesma matriz de rotação a cada peça.

Esta implementação é simples e tem algumas sutilezas:

1. A posição do objeto Piece mudará, mas suas cores não. Isso significa que você pode pedir a peça vermelho-verde, segurar o objeto, fazer algumas rotações e verificar o mesmo objeto para ver onde a peça vermelho-verde acabou.
2. Cada tipo de peça (borda, centro, canto) tem um padrão de coordenadas exclusivo. Para um cubo 3x3, uma peça de canto não tem zeros em seu vetor de posição ( (-1, 1, 1) ), uma aresta tem exatamente um zero ( (1, 0, -1) ) e uma peça central tem dois zeros ( (-1, 0, 0) ).
3. As matrizes de rotação que funcionam para um cubo 3x3 funcionarão para um cubo NxN.

Desvantagens:

1. A multiplicação de vetores matriciais é mais lenta que a troca de valores em matrizes.
2. Pesquisas de tempo linear para peças por posição. Você teria que armazenar Pieces em uma estrutura de dados externa e atualizá-la durante rotações para pesquisas de tempo constante por posição. Isso anula parte da elegância de usar matrizes de rotação e vaza a lógica de rotação para sua classe Cube. Se eu estivesse implementando qualquer tipo de algoritmo de resolução baseado em pesquisa, usaria outra implementação.
3. A análise de padrões (durante a solução) não é tão boa quanto poderia ser. Uma peça não tem conhecimento de suas peças adjacentes, e a análise seria lenta devido aos problemas de desempenho acima.

você pode usar uma matriz simples (cada elemento tendo um mapeamento de 1 para 1 para um quadrado em uma face) e simular cada rotação com uma certa permutação

você pode se safar com apenas 3 permutações essenciais: gire uma fatia com o eixo pela face frontal, gire o cubo ao redor do eixo vertical e gire o cubo sobre o eixo horizontal através das faces esquerda e direita. todos os outros movimentos podem ser expressos por alguma concatenação desses três.

a maneira mais direta de saber se um cubo é solucionável é resolvê-lo (encontre uma série de permutações que resolverão o cubo), se você acabar com 2 arestas que trocaram de lugar, uma única borda invertida, uma única canto virado ou 2 cantos trocados você tem um cubo unxolvable

A primeira condição que pode ser resolvida é que cada peça esteja presente e que as cores de cada peça possam ser usadas para montar um cubo "sovelado". Essa é uma condição relativamente trivial, cuja verdade pode ser determinada com uma lista de verificação simples. O esquema de cores em um cubo "padrão" é definido , mas mesmo que você não esteja lidando com cubo padrão há apenas 6! possíveis combinações de faces resolvidas.

Uma vez que você tenha todas as peças e cores certas, então é uma questão determinar se qualquer configuração física é solucionável. Nem todos eles são. A maneira mais ingênua de verificar isso é executar um algoritmo de resolução de cubo e ver se ele termina com um cubo resolvido. Eu não sei se existem técnicas combinatórias extravagantes para determinar a solubilidade sem realmente tentar resolver o cubo.

Quanto a qual estrutura de dados ... isso quase não importa. A parte complicada é obter as transformações corretas e ser capaz de representar o estado do cubo de uma maneira que permita trabalhar perfeitamente com os algoritmos disponíveis na literatura. Como o eixo de bordo indicou que existem três tipos de peças. A literatura sobre resolução de cubo de rubik sempre se refere a peças de seu tipo. Transformações também são representadas de formas comuns (procure por notação do Singmaster ). Além disso, todas as soluções que eu vi sempre se referem a uma peça como um ponto de referência (geralmente colocando a peça central branca na parte inferior).

Como você já recebeu ótimas respostas, deixe-me adicionar apenas um detalhe.

Independentemente da sua representação concreta, note que as lentes são uma excelente ferramenta para "aproximar" as várias partes de um cubo. Por exemplo, veja a função cycleLeft em este código de Haskell . É uma função genérica que ciclicamente permuta qualquer lista de comprimento 4. O código para executar o movimento L se parece com isto:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

Assim, cycleLeft opera na exibição dada por leftCols . Similarmente, rotateSideCW , que é uma função genérica tomando um lado para uma versão rotacionada, opera na visão dada por leftSide . Os outros movimentos podem ser implementados de maneira semelhante.

O objetivo da biblioteca do Haskell é criar imagens bonitas. Eu acho que conseguiu:

Você parece estar fazendo duas perguntas separadas.

1. How to represent a cube with X number of sides?

Se você vai simular um cubo Rubic do mundo real, então todos os cubos do Rubik têm 6 lados. Eu acho que o que você quer dizer é "X número de peças por dimensão por lado". Cada lado do cubo original do Rubic é 3x3. Outros tamanhos incluem 4x4 (Cubo do Professor), 5x5 e 6x6.

Eu representaria os dados com 6 lados, usando a notação de resolução de cubos "padrão":

• FRONT: o rosto voltado para o solucionador
• VOLTAR
• DIREITO
• ESQUERDA
• UP
• DOWN

Cada lado é uma matriz 2-D de X por X.

Gosto da ideia de @maple_shaft representar diferentes peças (mini-cubos) de forma diferente: as peças central, de borda e de canto têm 1, 2 ou 3 cores, respectivamente.

Eu representaria os relacionamentos entre eles como um gráfico (bidirecional), com bordas conectando peças adjacentes. Cada peça teria uma matriz de slots para bordas (conexões): 4 slots em peças centrais, 4 slots em peças de borda, 3 slots em peças de canto. Como alternativa, as peças centrais podem ter 4 conexões para as arestas e 4 para as peças de canto separadamente, e / ou as arestas podem ter 2 conexões para peças centrais e 2 para peças separadas separadamente.

Essas matrizes são ordenadas para que a iteração das bordas do gráfico sempre represente a mesma rotação, modulo a rotação do cubo. Ou seja, por exemplo para uma peça central, se você girar o cubo de forma que sua face fique no topo, a ordem das conexões será sempre no sentido horário. Da mesma forma para peças de borda e canto. Esta propriedade se mantém após as rotações do rosto (ou assim parece-me agora).

• Encontrar peças que pertencem a uma borda é trivial.
• Encontrar peças que pertencem a um rosto é trivial.
• Encontrar rostos que estão em determinada direção para determinada face, ou uma face oposta, está passando por 2 ou 3 links bem definidos.
• Para girar um rosto, atualize as conexões de todas as peças conectadas à peça central do rosto.

Detecção de condições claramente insolúveis (bordas truncadas / invertidas, canto trocado), se bem que seja fácil, porque encontrar partes de um tipo em particular e sua orientação é simples.

Que tal nós e ponteiros?

Supondo que sempre haja 6 faces e que 1 nó represente 1 quadrado em 1 face:

r , g , b
r , g , b
r , g , b
|   |   |
r , g , b - r , g , b
r , g , b - r , g , b
r , g , b - r , g , b

Um nó tem um ponteiro para cada nó ao lado dele. Uma rotação de círculo apenas migra o ponteiro (Número de nós / Número de faces) -1 nós ao longo, neste caso 2. Como todas as rotações são rotações de círculo, você apenas constrói uma função rotate . Ele é recursivo, movendo um espaço para cada nó e verificando se ele foi movido o suficiente, já que ele terá coletado o número de nós e sempre haverá quatro faces. Caso contrário, incremente o número de vezes que o valor foi movido e chame novamente para girar.

Não se esqueça de que está duplamente ligado, por isso atualize também os nós recém-apontados. Sempre haverá Height * Número de largura dos nós movidos, com um ponteiro atualizado por nó, portanto, deve haver Height * Width * 2 número de ponteiros atualizados.

Como todos os nós apontam um para o outro, basta percorrer um círculo atualizando cada nó à medida que você chega a ele.

Isso deve funcionar para qualquer cubo dimensionado, sem casos de borda ou lógica complexa. É apenas um ponteiro de caminhada / atualização.

A partir da experiência pessoal usando um conjunto para acompanhar cada parte rotacional do cubo funciona bem. Cada sub cubo está em três conjuntos sem mater do tamanho do cubo de rubik. Então, para encontrar um sub cubo, onde no cubo do rubik você apenas pega a interseção dos três conjuntos (o resultado é um sub cubo). Para fazer um movimento, remova os sub-filhotes afetados dos conjuntos envolvidos no movimento e, em seguida, coloque-os de volta nos conjuntos que os pegam como resultado do movimento.

O cubo 4 por 4 terá 12 conjuntos. 6 conjuntos para 6 faces e 6 conjuntos para as seis bandas que circundam o cubo. Cada um dos rostos tem 16 sub-cubos e cada uma das bandas tem 12 sub-filhotes. Há um total de 56 subcubos. Cada sub cubo contém informações sobre a cor e a direção das cores. O cubo de rubik em si é um array de 4 por 4 por 4, com cada elemento tendo informações consistindo dos 3 conjuntos que definem o sub-cubo naquele local.

Diferentemente das outras 11 respostas, essa estrutura de dados permite que você use a interseção de conjuntos para definir a localização de cada subpunho no cubo. Isso economiza o trabalho de atualizar os sub blocos próximos quando uma alteração é feita.