Bolas coloridas em uma grade 4x4

Question

As bolas coloridas são colocadas em uma grade 4x4. Um movimento consiste em trocar duas bolas adjacentes (horizontal ou verticalmente). Qual é o menor número de movimentos necessários para formar 4 componentes conectados *, um para cada cor na grade a seguir?

* Aqui, um componente conectado é uma coleção de bolas da mesma cor, de modo que haja um caminho de degraus horizontais ou verticais de qualquer bola para qualquer outra bola.

Answer 1

8 movimentos:

1-3: Mova o R solitário três vezes para a direita para conectar os Rs.

Y G B R
G B G R
Y G Y R
G B R R

4-6: Mova os Bs para pontos não R na coluna 3.

Y G B R
G G B R
Y Y B R
G G R R

7-8: Agrupe os amarelos na coluna 1

Y G B R
Y G B R
Y G B R
G G R R

Answer 2

Isso pode ser feito em

9 movimentos

que acredito estar bem perto do ideal, se já não estiver.

Denotando as quatro cores como R, G, B, Y respectivamente, o estado inicial é

Y G B R
G B G R
R Y G Y
G B R R

Agora,

Mova o solitário R três vezes para a direita para conectar os Rs.

Y G B R
G B G R
Y G Y R
G B R R

Então,

Conecte os Y's em três movimentos, alinhando-os na primeira coluna. (Mova R3C1 uma vez para cima e, em seguida, R3C3 para a esquerda duas vezes.) É possível conectá-los em dois movimentos, mas então custará mais movimentos para conectar G e B.

Y G B R
Y B G R
Y G G R
G B R R

Finalmente,

Conecte o G na seção inferior em três movimentos. (Mova R3C2 para baixo uma vez e R1C2 para baixo duas vezes.)

Y B B R
Y B G R
Y G G R
G G R R

Answer 3

Duas soluções bonitas com resultados simétricos de espelho e rotação:

Nas coordenadas do tabuleiro de xadrez (canto superior esquerdo é a4): 1. a4-b4 2. b4-c4 3. b2-c2 4. c2-c3 5. a2-b2 6. b2-c2 7. c2-d2 8. b1- b2
gbyr
gbyr
gbyr
ggrr

1. b2-c2 2. c3-c4 3. c2-c3 4. a4-b4 5. b4-c4 6. a2-b2 7. b2-c2 8. c2-d2
ggyr
gbyr
gbyr
gbrr

Nota sobre otimização:

8 movimentos parecem ser o mínimo. Meu solucionador de força bruta encontra 8 soluções de movimento, mas não encontra 7 soluções de movimento.

Answer 4

Como a pergunta não exige que todas as bolas façam parte de um componente, irei com 3 lances.

YGBR
GBGR
RYGY
GBRR

para

YGBR
G Y GR
R B GY
GBRR

para

Y Y BR
G G GR
RBGY
GBRR

e

YYBR
GGGR
RBG R
GBR Y

Compenentes são

YY B R
GGG R
R B G R
G B RY

Se mais de 4 componentes forem permitidos, a última etapa não será necessária e a contagem total será 2.