Se estou tentando simular um cubo de Rubik , como você criaria uma estrutura de dados para armazenar o estado do cubo na memória, com um número X de blocos por lado?
Coisas a considerar:
- o cubo pode ser de qualquer tamanho
- é um cubo de Rubik, então as camadas podem ser giradas
data-structures
Mel
fonte
fonte
Respostas:
O que há de errado com uma matriz de tamanho antiga simples
[6X][X]
? Você não precisa saber sobre mini-cubos internos , porque não os vê; eles não fazem parte do estado do cubo. Esconda dois métodos feios por trás de uma interface bonita e simples de usar, teste-a até a morte e pronto, pronto!fonte
As long as you know how the six surfaces are "threaded" together
Qual é exatamente o que uma estrutura de dados mais robusta fornecerá. Acho que estamos discutindo a mesma coisa. Um lado da matriz e um lado como uma matriz de blocos, no entanto, existem muitas propriedades interessantes sobre lados e blocos que ajudam a descobrir que "encadeamento" não gosta muito desse termo porque pode ser confundido com o encadeamento múltiplo; )Deve-se notar que sou um cubo de velocidade ávido, mas nunca tentei representar programaticamente 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:
Bloco de canto - Possui três faces coloridas e três peças adjacentes com as quais compartilhará um lado a qualquer momento.
Edge Block - Possui duas faces coloridas e quatro 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.
Bloco central - Em um cubo 3x3, esta peça não é móvel, mas pode ser girada. Sempre terá 4 blocos de borda adjacentes. Em cubos maiores, existem vários blocos centrais que podem ser compartilhados com outro bloco central ou uma peça de aresta. Os 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 em que 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 todas as faces 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 execute uma transformação de rotação em cada face, movendo os blocos apropriados para dentro e para fora das listas apropriadas.
EDIT: Nota importante, essas listas devem ser ordenadas, é claro, mas eu esqueci de mencionar isso. Por exemplo, se eu virar o lado direito, o bloco do lado esquerdo do canto esquerdo se moverá para o canto direito do lado direito e será girado no sentido horário.
fonte
list of lists
. talvez seja melhor ter apenas uma lista não ordenada de blocos que você pode consultar. e você apenas atualiza as referências de bloco adjacentes ao executar uma transformação. Se você quiser uma lista de todos os blocos em uma face, poderá consultar sua lista para todos os blocos adjacentes aos blocos centrais, certo?Quando penso nesse problema, penso em um cubo estático com as cores se movendo em padrões conhecidos. Assim....
Um objeto Cube contém 6 objetos Side que permanecem fixos indexados de 0 a 5. Cada lado contém 9 objetos de posição que permanecem fixos indexados de 0 a 8. Cada posição contém uma cor.
Para simplificar, lide com cada ação em incrementos de um quarto de volta. Existem 3 eixos de rotação, cada um em 2 direções possíveis, para um total de 6 ações possíveis no cubo. Com essas informações, torna-se uma tarefa bastante simples mapear as 6 ações possíveis no cubo.
Portanto, a cor verde no lado 6, posição 3, pode passar para o lado 1, posição 3, ou lado 2, posição 7, entre outras, dependendo da ação tomada. Eu não explorei isso o suficiente para encontrar traduções matemáticas, mas provavelmente surgirão padrões dos quais você pode tirar proveito no código.
Para fazer isso, nunca comece com um estado de cubo aleatório. Em vez disso, comece com um estado resolvido e execute n ações programaticamente para obter o cubo em um estado inicial aleatório. Como você só tomou ações legais para chegar ao estado atual, o cubo deve ser solucionável.
fonte
Eu achei um sistema de coordenadas xyz uma maneira simples de abordar o cubo de Rubik e as 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 de vetores de matriz). A peça também mantém o controle das cores em uma tupla(cx, cy, cz)
, fornecendo as cores voltadas ao longo de cada eixo. Uma pequena quantidade de lógica garante que essas cores sejam atualizadas adequadamente durante uma rotação: uma rotação de 90 graus no plano XY significa que trocamos os valores decx
ecy
.Como toda a lógica de rotação está encapsulada na classe Piece, o Cubo 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 em cada peça.
Esta implementação é simples e possui algumas características:
(-1, 1, 1)
), uma aresta possui exatamente um zero ((1, 0, -1)
) e uma peça central possui dois zeros ((-1, 0, 0)
).Desvantagens:
fonte
você pode usar uma matriz simples (cada elemento com um mapeamento de 1 para 1 para um quadrado em uma face) e simular cada rotação com uma certa permutação
você pode sair com apenas três permutações essenciais: gire uma fatia com o eixo pela face frontal, gire o cubo em torno do eixo vertical e gire o cubo sobre o eixo horizontal pelas 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ê tiver duas arestas que foram trocadas de lugar, uma única aresta invertida, um único canto invertido ou 2 cantos trocados você tem um cubo unololvable
fonte
the most straightforward way of know whether a cube is solvable is to solve it
. Bem, usando o modelo que você sugere, acho que é verdade. Mas se você usar um modelo mais próximo do @ maple_shaft e rastrear rotações, poderá testar rapidamente se um cubo 3x3x3 é solucionável verificando a soma dos flips de borda mod 2 é 0 e as rotações de canto mod 3 são 0. Em seguida, verifique a paridade da permutação por contando swaps de borda e swaps de canto (necessários para voltar a resolver), sua soma mod 2 deve ser 0 (paridade total par). Esses são os testes necessários e suficientes para provar que o cubo é solucionável.A primeira condição para ser solucionável seria que cada peça estivesse presente e que cores em cada peça pudessem ser usadas para montar um cubo "sovled". Essa é uma condição relativamente trivial, cuja verdade pode ser determinada com uma simples lista de verificação. O esquema de cores em um cubo "padrão" é definido , mas mesmo que você não esteja lidando com cubos padrão, existem apenas 6! combinações possíveis de faces resolvidas.
Depois de acertar todas as peças e cores, é uma questão de determinar se uma determinada configuração física é solucionável. Nem todos eles são. A maneira mais ingênua de verificar isso é executar um algoritmo de solução de cubo e ver se ele termina com um cubo resolvido. Não sei se existem técnicas combinatórias sofisticadas para determinar a solvabilidade sem realmente tentar resolver o cubo.
Quanto à estrutura de dados ... isso quase não importa. A parte complicada é acertar as transformações e ser capaz de representar o estado do cubo de uma maneira que permita trabalhar com os algoritmos disponíveis na literatura. Como o Maple-shaft indicou, existem três tipos de peças. A literatura sobre a solução de cubos de rubik sempre se refere a peças por tipo. As transformações também são representadas de maneiras comuns (consulte a notação Singmaster ). Além disso, todas as soluções que vi sempre se referem a uma peça como ponto de referência (geralmente colocando a peça central branca na parte inferior).
fonte
Como você já recebeu ótimas respostas, deixe-me adicionar apenas um detalhe.
Independentemente da sua representação concreta, observe que as lentes são uma ferramenta muito boa para "aumentar o zoom" nas várias partes de um cubo. Por exemplo, olhe para a função
cycleLeft
em este código Haskell . É uma função genérica que permite ciclicamente qualquer lista de comprimento 4. O código para executar o movimento L se parece com o seguinte:Assim,
cycleLeft
opera na visão dada porleftCols
. Da mesma forma,rotateSideCW
que é uma função genérica que está do lado de uma versão rotacionada dela, opera na visão dada porleftSide
. Os outros movimentos podem ser implementados de maneiras semelhantes.O objetivo dessa biblioteca Haskell é criar imagens bonitas. Eu acho que conseguiu:
fonte
Você parece estar fazendo duas perguntas separadas.
Se você simular um cubo de Rubic do mundo real, todos os cubos de Rubik terão 6 lados. Eu acho que você quer dizer "número X de peças por dimensão por lado". Cada lado do cubo de Rubic original é 3x3. Outros tamanhos incluem 4x4 (Cubo do professor), 5x5 e 6x6.
Eu representaria os dados com 6 lados, usando a notação de solução de cubo "padrão":
Cada lado é uma matriz 2D de X por X.
fonte
Gosto da idéia do @maple_shaft representar peças diferentes (minicubos) de maneira diferente: as peças central, de aresta e de canto têm 1, 2 ou 3 cores, respectivamente.
Eu representaria os relacionamentos entre eles como um gráfico (bidirecional), com arestas conectando peças adjacentes. Cada peça teria uma matriz de slots para arestas (conexões): 4 slots em peças centrais, 4 slots em peças de borda, 3 slots em peças de canto. Alternativamente, as peças centrais podem ter 4 conexões com as peças de aresta e 4 para peças de canto separadamente, e / ou as peças de aresta podem ter 2 conexões com as peças centrais e 2 com as peças de canto separadamente.
Essas matrizes são ordenadas para que a iteração sobre as arestas do gráfico sempre represente a mesma rotação, modulando a rotação do cubo. Ou seja, por exemplo, para uma peça central, se você girar o cubo para 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. Essa propriedade se mantém após as rotações da face (ou assim parece-me agora).
A detecção de condições claramente insolúveis (bordas trocadas / invertidas, cantos trocados) também é esperançosamente fácil, porque encontrar peças de um tipo específico e sua orientação é simples.
fonte
E nós e ponteiros?
Supondo que sempre haja 6 faces e que 1 nó represente 1 quadrado em 1 face:
Um nó possui um ponteiro para cada nó próximo a ele. Uma rotação de círculo apenas migra o ponteiro (Número de nós / Número de faces) -1 nós, neste caso 2. Como todas as rotações são rotações de círculo, você apenas cria uma
rotate
função. É recursivo, movendo cada nó um espaço e verificando se os moveu o suficiente, pois ele coletou o número de nós e sempre há quatro faces. Caso contrário, aumente o número de vezes que o valor foi movido e ligue novamente.Não esqueça que ele é duplamente vinculado; portanto, atualize também os nós recém-apontados. Sempre haverá Altura * Número de nós movidos, com um ponteiro atualizado por nó; portanto, deve haver Altura * Largura * 2 número de ponteiros atualizados.
Como todos os nós apontam um para o outro, apenas circule atualizando cada nó à medida que você chega a ele.
Isso deve funcionar para qualquer cubo de tamanho, sem arestas ou lógica complexa. É apenas uma caminhada / atualização do ponteiro.
fonte
Por experiência pessoal, usar um conjunto para acompanhar cada parte rotacional do cubo funciona bem. Cada subcubo possui três conjuntos, sem o tamanho do cubo de rubik. Então, para encontrar um subcubo em algum lugar do cubo de rubik, basta fazer a interseção dos três conjuntos (o resultado é um subcubo). Para fazer um movimento, remova os sub-cubos afetados dos conjuntos envolvidos no movimento e, em seguida, coloque-os novamente nos conjuntos que os levam como resultado da movimentação.
O cubo 4 por 4 terá 12 conjuntos. 6 conjuntos para as 6 faces e 6 conjuntos para as seis faixas que circundam o cubo. Cada uma das faces possui 16 subcubos e as bandas cada um com 12 subcubos. Há um total de 56 subcubos. Cada subcubo contém informações sobre cores e a direção das cores. O próprio cubo de rubik é uma matriz de 4 por 4 por 4, com cada elemento tendo informações que consistem nos 3 conjuntos que definem o subcubo nesse 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 sub-bloco no cubo. Isso economiza o trabalho de ter que atualizar os sub-blocos próximos quando uma alteração é feita.
fonte