Permutation Puzzle Swap Cubies

Question

Recentemente, lancei um quebra-cabeça online RAVEL . É uma matriz 3D de cubos que devem ser organizados em ordem de cores. Uma jogada legal é deslizar uma linha, coluna ou pista por qualquer número de espaços. Os cubos que são empurrados para fora são inseridos na outra extremidade.

Eu sugiro que você visite RAVEL , clique na guia "Experimenter" e experimente alguns RAVELs de várias dimensões para que você possa apreciar melhor o que se segue.

Eu conjecturo que todas as permutações podem ser resolvidas, mas como não sei ao certo, embaralhei o RAVEL com uma série de movimentos legais aleatórios.

Pergunta um:

É necessário embaralhar com movimentos legais? Ou poderia simplesmente embaralhar com trocas aleatórias e ainda assim ser solucionável? Dito de outra forma: a conjectura é verdadeira, todas as permutações podem ser resolvidas?

Minha segunda pergunta tem a ver com técnicas de solução. Eu resolvo RAVELs camada por camada usando métodos ad hoc para mover os cubos para o lugar sem alterar as posições dos já colocados. Mas, na última camada, uso métodos formalizados para os últimos cubos.

O algoritmo do Ciclo 3

Este algoritmo faz o ciclo das posições de três cubos, deixando todos os outros cubos no lugar. O espaço entre os três cubos não importa, desde que formem um ângulo reto: cubos 1 e 2 na mesma linha, cubos 2 e 3 na mesma coluna.

O algoritmo:

• Arraste o cubo verde para o ápice (posição azul).
• Arraste o vermelho para a posição do ápice.
• Arraste o vértice para onde o verde começou.
• Arraste o vértice para onde o vermelho começou.

Os números na imagem mostram a sequência de movimentos. Para circular na direção oposta, troque 1 com 2 e troque 3 com 4.

Trocar dois cubos

Freqüentemente, você pode terminar de resolver o RAVEL usando apenas os procedimentos acima. Mas às vezes os pares de cubos trocados permanecem. Não conheço um algoritmo geral para trocar pares que funcione para todos os tamanhos de RAVEL. Consegui resolver alguns exemplos simplesmente me debatendo, tentando de tudo.

Eu encontrei um procedimento para fazer uma troca de par em RAVELs onde uma das dimensões é igual a 4.

A imagem mostra a sequência de movimentos para trocar os cubinhos vermelhos e verdes. A dimensão vertical deve ser quatro.

Questão dois:

Você pode criar um algoritmo de troca de par que funcione para RAVELs de todos os tamanhos?

☺ ☺ ☺

Answer 1

Este quebra-cabeça é uma versão 3D de um que está disponível na coleção de quebra-cabeças de Simon Tatham com o nome de Sixteen . Este quebra-cabeça foi discutido aqui antes: Técnicas para resolver quebra-cabeças deslizantes de coluna de linha

A resposta aqui também se aplica aqui, então não vou entrar em muitos detalhes.

Questão 1:

Cada permutação com paridade par é possível e facilmente resolvida usando os 3 ciclos. Se todas as dimensões são ímpares, então cada movimento é uma permutação par, então nenhuma permutação ímpar é possível. Em particular, nenhuma troca única é possível nesse caso. Se pelo menos uma dimensão for par, então as permutações ímpares também estão disponíveis, então todas as permutações podem ser resolvidas.

Questão 2:

Se uma ou mais dimensões forem pares, então uma mudança ao longo de tal dimensão é uma permutação ímpar. Portanto, você pode fazer essa mudança e resolver a maioria das peças deslocadas com 3 ciclos e ficar com uma única troca.
Suponha que A seja um movimento que muda uma linha contendo$2n$ blocos, B é um deslocamento de uma linha de intersecção de blocos, e B 'é o inverso de B. Em seguida, a sequência de movimento BAB'A repetida $n-1$ vezes, seguido de BAAB'A, terá o efeito de trocar dois blocos adjacentes na linha A.