# Colored balls in a 4x4 grid

Colored balls are placed in a 4x4 grid. A move consists of swapping two adjacent (horizontally or vertically) balls. What is the least number of moves required to form 4 connected components*, one for each color in the following grid?

*Here a connected component is a collection of balls of the same color, such that there is a path of horizontal or vertical steps from any ball to any other ball.

• I'd be interested in seeing the generalized version of this: Given a 4x4 grid containing balls in 4 colors (at least 1 ball in each color), what is the maximum number of moves that would be required to group them all such that there is one contiguous group for each color? (i.e. what starting configuration would have the highest minimum number of moves? It appears to be 8 for this configuration, but how high can we make that?) Nov 9 '20 at 18:11

8 moves:

1-3: Move the lonely R three times to the right to connect the R's.

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

4-6: Move the Bs to non-R spots in column 3.

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

7-8: Group the yellows in column 1

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

• Well done! Well I finally wrote a solver that verifies that this is the optimal answer. So I can finally give you the tick :) Nov 13 '20 at 1:35

This can be done in

9 moves

which I believe is pretty close to optimal, if not already.

Denoting the four colors as R, G, B, Y respectively, the initial state is

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

Now,

Move the lonely R three times to the right to connect the R's.

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

Then,

Connect the Y's in three moves, aligning them in the first column. (Move R3C1 once upwards, and then R3C3 left twice.) It's possible to connect them in two moves, but then it will cost more moves to connect G and B.

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

Finally,

Connect the G at the lower section in three moves. (Move R3C2 down once, and R1C2 down twice.)

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

Two pretty solutions with mirror and rotation symmetric outcomes:

In checker board coordinates (top left is 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
g b y r
g b y r
g b y r
g g r r

1. b2-c2 2. c3-c4 3. c2-c3 4. a4-b4 5. b4-c4 6. a2-b2 7. b2-c2 8. c2-d2
g g y r
g b y r
g b y r
g b r r

Note on optimality:

8 moves appears to be the minimum. My brute-force solver finds 8 move solutions but no 7 move solutions.

Since the question does not request that all of the balls are part of a component, I will go with 3 moves.

YGBR
GBGR
RYGY
GBRR

to

YGBR
GYGR
RBGY
GBRR

to

YYBR
GGGR
RBGY
GBRR

and

YYBR
GGGR
RBGR
GBRY

Compenents are

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

If more than 4 components are allowed, the last step is not necessary, and the total count is 2.

• "Since the question does not request that all of the balls are part of a component", yeah, I also noticed that in the question. I think the question can be improved, since it does not look like this is the intention. Nov 9 '20 at 20:03
• no each ball MUST be part of a component, because the question asks for 4 components one for each colour Nov 9 '20 at 22:53