Цветные шары в сетке 4х4

Question

Цветные шары размещаются в сетке 4х4. Ход состоит из обмена двух соседних (по горизонтали или вертикали) шаров. Какое наименьшее количество ходов требуется для формирования 4 связанных компонентов *, по одному для каждого цвета в следующей сетке?

* Здесь компонент связности - это набор шаров одного цвета, так что от любого шара к любому другому шару проходит путь горизонтальных или вертикальных ступенек.

Answer 1

8 ходов:

1-3: Переместите одинокую R три раза вправо, чтобы соединить R.

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

4-6: Переместите B в места, отличные от R в столбце 3.

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

7-8: Сгруппируйте желтые в столбец 1.

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

Answer 2

Это можно сделать в

9 ходов

что я считаю довольно близким к оптимальному, если не уже.

Обозначая четыре цвета как R, G, B, Y соответственно, начальное состояние

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

В настоящее время,

Переместите одинокую R три раза вправо, чтобы соединить R.

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

Потом,

Соедините Y за три хода, совместив их в первом столбце. (Переместите R3C1 один раз вверх, а затем дважды влево R3C3.) Их можно соединить за два хода, но тогда для соединения G и B потребуется больше ходов.

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

В заключение,

Соедините букву G в нижней части за три хода. (Переместите R3C2 вниз один раз и R1C2 дважды.)

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

Answer 3

Два красивых решения с зеркально-симметричным результатом:

В координатах шахматной доски (вверху слева - 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

Обратите внимание на оптимальность:

8 ходов - это минимум. Мой решатель методом перебора находит 8 ходов, но не 7 ходов.

Answer 4

Поскольку вопрос не требует, чтобы все шары были частью компонента, я выберу 3 хода.

YGBR
GBGR
RYGY
GBRR

к

YGBR
G Y GR
R B GY
GBRR

к

Y Y BR
G G GR
RBGY
GBRR

и

YYBR
GGGR
RBG R
GBR Y

Компоненты

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

Если разрешено более 4 компонентов, последний шаг не требуется, и общее количество составляет 2.