Vamos mudar CORONA!

Question

Aqui está um quebra-cabeça deslizante com 6 blocos em uma grade 2x4.

Você pode mover cada bloco. Mas o bloco em forma de 8 com dois O's não pode ser movido separadamente.

Observe que o bloco em forma de 8 pode ser movido para uma posição vertical ou horizontal. Esse bloco é chamado de carro Conway: ele se move em zigue-zague nas curvas de 90 graus. Portanto, este problema é uma homenagem a John Horton Conway de alguma forma, que morreu devido a complicações do COVID-19.

Em que você pode mudar o CORONA? Qual é o número mínimo de etapas?

Answer 1

É conhecido que, para qualquer quebra-cabeça deslizante retangular simples (maior que 2x2), qualquer configuração em conformidade com a paridade é alcançável a partir do estado resolvido, e todas aquelas com paridade incorreta são inacessíveis. "Em conformidade com a paridade" significa que a paridade de todo o tabuleiro, mais a distância Manhattan do buraco de sua posição resolvida, deve ser uniforme. Informações relevantes podem ser encontradas na Wikipedia e no MathWorld .

O tabuleiro CORONA tem duas distinções de um tabuleiro 2x4 simples: há dois O's e eles estão presos um ao outro. Observei que o OO vertical no meio pode mudar sua própria paridade, mas apenas alterando a localização do furo (em relação ao OO vertical de bloqueio) ao mesmo tempo. Quando OO está em algum lugar na borda (horizontal ou vertical), parece que o par pode ter apenas uma orientação.

Prova informal

Para trocar dois O's no lugar, precisamos mover a peça como uma junção em T.

?? O1 ?? ??  =>  ?? ?? ?? ??  =>  ?? ?? ?? ??  =>  ?? O2 ?? ??
?? O2 ?? ??      O2 O1 ?? ??      ?? O2 O1 ??      ?? O1 ?? ??

No entanto, observe que o primeiro movimento requer um buraco no lado esquerdo e o terceiro requer um buraco no lado direito. Um buraco não pode se mover através da peça vertical sem mover a peça vertical primeiro.

Além disso, suponha que o primeiro estado tenha o buraco à sua esquerda. Independentemente de como você move os buracos, mover o OO resultará em um dos seguintes estados:

O1 O2 ?? ??  or  ?? ?? ?? ??
?? ?? ?? ??      O2 O1 ?? ??

e movê-lo do último estado resultará em um dos seguintes:

?? O1 O2 ??  or  ?? ?? ?? ??
?? ?? ?? ??      ?? O2 O1 ??

todos os quais orientam O2 no sentido horário a partir de O1. Não há como alterar a orientação de OO na borda.

Para resumir todos os itens acima, dada a posição do OO e do furo, a orientação do OO é fixa. Isso significa que o argumento da paridade se aplica mesmo que dois O's estejam presentes, declarando todos os estados de paridade ímpar inalcançáveis.

Acho que provar que todos os estados de paridade par são alcançáveis ​​é fácil: basta passar por um estado em que OO é colocado verticalmente no lado esquerdo e mover livremente a parte 2x3 restante do tabuleiro.

---

Agora, para a tarefa real. Se não palavras forem permitidas,

Posso obter o CRAOON em 16 etapas:

         1            4            1            3
C O R x  =>  C . R x  =>  C R x A  =>  C R x A  =>
. O N A      O O N A      O O . N      . O O N
         1            4            1            1
R x . A  =>  R x O A  =>  C R O A  =>  C R . A  =>  C R A .
C O O N      C . O N      x . O N      x O O N      x O O N

Para uma palavra real,

Estou recebendo CORONA novamente, em 19 movimentos (começando com o estado após 15 movimentos):

         2            2
C R . A  =>  C O R A  =>  C O R .
x O O N      x O . N      x O N A

Acho que a mensagem deste quebra-cabeça é que

CORONA é persistente .

---

jafe sugeriu a palavra (então confirmado por OP)

GUAXINIM

o que acabou sendo possível, mas aparentemente muito distante (ligeiramente melhorado após a edição):

Demorou 32 30 28 movimentos .

         3            3            3            3
C O R x  =>  O C R x  =>  O . C x  =>  O N . x  =>
. O N A      O . N A      O N R A      O R C A
         5            11
O N x A  =>  O x R A  =>  R A C .
O R . C      O . N C      x O O N

30 jogadas:

         1            5            6            4
C O R x  =>  C . R x  =>  C R x A  =>  R x A N  =>
. O N A      O O N A      . O O N      C . O O
         5            6            3
R A N O  =>  A C N O  =>  R A C N  =>  R A C .
C x . O      R . x O      . x O O      x O O N

32 movimentos:

         2            2            2            4
C O R x  =>  O O R x  =>  O . R x  =>  O R N x  =>
. O N A      C . N A      O C N A      O C . A
         4            3            6            9
O R A N  =>  O A C N  =>  O A . C  =>  O x R C  =>  R A C .
O C . x      O R . x      O R x N      O . A N      x O O N

De acordo com o resultado da pesquisa de anagramas no Qat , as duas palavras já apresentadas são as únicas palavras alcançáveis.

CAROON tem paridade errada (porque RACOON é alcançável e CAROON é RACOON com R e C trocados), e ORACON separaria os dois O's.

Answer 2

Comentário do OP:

Você pode ver a resposta movendo o arquivo gif. 28 movimentos.