Como representar um cubo de Rubik em uma estrutura de dados

58

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
Mel
fonte
2
Dever de casa? Ou um problema do mundo real ...
SDG
4
Você pode estar interessado no código-fonte desse cubo de Rubik Solver .
Mouviciel 3/04
22
Tenho a certeza de que o número de um cubo de lados deve ser de 6
Simon Bergot
3
Eu ficaria curioso para ver um modelo do Cubo de Rubik achatado para poder ver todos os lados simultaneamente. Hmm, estou tentado a escrever isso agora. Poderia ter a forma de um T ou até azulejos sem fim, se possível (ainda não pensei nisso).
Lee Kowalkowski
6
Sinto-me tentado a citar Eric Evans, (citação provavelmente não é 100% correto, uma vez que é citado a partir da memória) "Modelos não são nem certo, nem errado Eles são simplesmente mais ou menos úteis."
Pete

Respostas:

37

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!

dasblinkenlight
fonte
31
mesmo um cubo de Rubik real não possui minicubos internos
jk.
8
Isso funcionará, mas seu algoritmo provavelmente será excessivamente complexo para acomodar uma estrutura de dados tão simples.
Maple_shaft
6
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; )
maple_shaft
7
@maple_shaft "Qual é exatamente o que uma estrutura de dados mais robusta fornecerá a você." Eu não sei sobre isso: uma estrutura de dados com mais "estrutura" para ele seria necessariamente trazer adicional incidental complexidade relacionada à criação, manutenção e acesso a partes individuais dessa estrutura. É difícil dizer o que seria mais complexo - implementar turnos feios em uma matriz simples com algumas caixas de esquina mais uma "carona" no acesso a células individuais, ou uma estrutura com turnos um pouco menos complexos e leituras um pouco mais complexas.
precisa saber é o seguinte
16
Como alguém que realmente escreveu programas para manipular um cubo de Rubik, adotei a abordagem simples de usar seis matrizes bidimensionais, uma por face. É verdade que você precisa implementar algumas operações fundamentais no cubo que são um pouco irritantes, mas depois disso você fica livre para esquecer a representação. Isso nunca foi um problema para mim. Muitas vezes me perguntei como outras representações funcionariam da perspectiva do desempenho, mas nunca me senti sobrecarregado da perspectiva da codificação.
PeterAllenWebb
39

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:

  1. Bloco de canto - Possui três faces coloridas e três peças adjacentes com as quais compartilhará um lado a qualquer momento.

  2. 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.

  3. 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.

maple_shaft
fonte
concorda que cada bloco precisaria ter propriedades únicas. mas a transformação não seria tediosa porque você precisa atualizar as referências aos blocos adjacentes e ao seu 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?
Mel
@Mel É possível fazer isso de qualquer maneira, mas depois de conversar com o dasblinkenlight, acho que a abordagem dele seria menos complexa. Eu gostaria que a resposta dele tivesse mais votos que a minha. Eu não sou tão bom com algoritmos e o mais eficiente, eu realmente gosto de cubos de rubiks e os coleciono (mais de 40 tipos diferentes de todo o mundo).
Maple_shaft
Embora a resposta de dasblinknenlight a solução mais simples, eu estou concedendo-lhe a recompensa porque eu gosto do fato de sua resposta inclui alguns dos lógica que seria necessário para uma tal estrutura de dados, e os diferentes atributos do bloco
Rachel
Esse modelo de dados é mais fiel à realidade, mas torna algumas das operações simples que você gostaria de fazer mais do que deveriam: apenas para obter o estado do cubo seria necessário percorrer recursivamente as listas de cubos, o que é complicado.
Ziv 4/15
@ Ziv True, no entanto, a pergunta estava perguntando sobre a estrutura de dados e não necessariamente sobre os algoritmos.
maple_shaft
13

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.

Usando a estrutura de dados, como posso saber se um determinado cubo em um determinado estado é solucionável? Eu mesmo tenho lutado com essa pergunta e ainda não encontrei a resposta.

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.

Matthew Vines
fonte
11
Conselho clássico "você não quer começar daqui"!
precisa saber é o seguinte
8

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 de cxe cy.

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. A posição de um objeto Piece mudará, mas suas cores não. Isso significa que você pode solicitar a peça verde-vermelha, agarrar-se ao objeto, fazer algumas rotações e verificar o mesmo objeto para ver onde a peça verde-vermelha terminou.
  2. Cada tipo de peça (aresta, centro, canto) possui um padrão de coordenadas exclusivo. Para um cubo 3x3, uma peça de canto não possui zeros em seu vetor de posição ( (-1, 1, 1)), uma aresta possui exatamente um zero ( (1, 0, -1)) e uma peça central possui 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 em tempo linear para peças por posição. Você precisaria armazenar peças em uma estrutura de dados externa e atualizá-la durante as rotações para pesquisas em 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 na sua classe Cube. Se eu estivesse implementando qualquer tipo de algo para resolver algo baseado em pesquisa, usaria outra implementação.
  3. A análise de padrões (durante a resoluçã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.
user156217
fonte
3
Descobri que esse tipo de implementação funciona melhor para representar o cubo em um programa de gráficos 3D. A multiplicação da matriz possibilita animar as rotações da camada. Veja este repositório do github para obter um exemplo de implementação dessa abordagem. Estou considerando que, para adicionar um solucionador ao meu cubo 3D, precisarei de um algoritmo e estrutura de dados de uma das outras respostas.
Jonathan Wilson
5

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

catraca arrepiante
fonte
11
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.
precisa saber é o seguinte
3

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).

Angelo
fonte
11
Para o ponto 2, em vez de começar com um cubo aleatório e verificar se é solucionável. Eu começaria com um cubo resolvido e executaria n ações aleatórias no cubo para colocá-lo em um estado aleatório.
Matthew videiras
Sim, absolutamente, essa é a maneira mais simples de gerar uma configuração fisicamente possível de resolver. Começar com uma configuração arbitrária e determinar se é solucionável é definitivamente um problema separado, mas relacionado.
Angelo
2
Você conjetura que pode haver "técnicas sofisticadas" para determinar se um cubo é aquele que pode ser resolvido; de fato existem. Se você desmontar um cubo, mas mantiver os adesivos e remontar o cubo, não obterá necessariamente um cubo que seja solucionável; de fato, as probabilidades são de um a doze contra o fato de você ter um cubo solucionável. Você pode determinar se está em um estado solucionável por meio de uma análise de paridade das arestas e cantos; você realmente não precisa tentar resolver o cubo.
precisa
11
Aqui está uma breve visão geral dos três tipos de propriedades de paridade do cubo que devem ser preservadas para que o cubo seja solucionável. ryanheise.com/cube/cube_laws.html .
precisa
11
Eu postei essa pergunta no site da stackexchange de
Mel
3

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 cycleLeftem 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:

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

Assim, cycleLeftopera na visão dada por leftCols . Da mesma forma, rotateSideCWque é uma função genérica que está do lado de uma versão rotacionada dela, opera na visão dada por leftSide. Os outros movimentos podem ser implementados de maneiras semelhantes.

O objetivo dessa biblioteca Haskell é criar imagens bonitas. Eu acho que conseguiu: A biblioteca diagrams-rubiks-cube em ação

Ingo Blechschmidt
fonte
2

Você parece estar fazendo duas perguntas separadas.

  1. Como representar um cubo com um número X de lados?

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":

  • FRENTE: o rosto voltado para o solucionador
  • DE VOLTA
  • DIREITO
  • ESQUERDA
  • ACIMA
  • BAIXA

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

B Seven
fonte
Você pode comprar um cubo 17x17 ! Ele tem alguns compromissos mecânicos, mas é isomórfico para a coisa real.
RBerteig 03/04
1

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).

  • Encontrar peças pertencentes a uma aresta é trivial.
  • Encontrar peças pertencentes a um rosto é trivial.
  • Encontrar faces que estão em uma determinada direção, ou uma face oposta, está atravessando 2 ou 3 links bem definidos.
  • Para girar uma face, atualize as conexões de todas as peças conectadas à peça central da face.

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.

9000
fonte
1

E 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ó 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 rotatefunçã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.

Spencer Rathbun
fonte
-1

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.

mártir forte
fonte
este não parece oferecer nada substancial sobre os pontos feitos e explicado em antes 11 respostas
mosquito