8
$\begingroup$

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?

enter image description here

*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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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?) $\endgroup$
    – Darrel Hoffman
    Nov 9, 2020 at 18:11
  • $\begingroup$ @DarrelHoffman great idea! I've made a new puzzle about this: puzzling.stackexchange.com/questions/104682/… $\endgroup$
    – Dmitry Kamenetsky
    Nov 10, 2020 at 1:01

4 Answers 4

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well done! Well I finally wrote a solver that verifies that this is the optimal answer. So I can finally give you the tick :) $\endgroup$
    – Dmitry Kamenetsky
    Nov 13, 2020 at 1:35
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$
    – Andrew Savinykh
    Nov 9, 2020 at 20:03
  • $\begingroup$ no each ball MUST be part of a component, because the question asks for 4 components one for each colour $\endgroup$
    – Dmitry Kamenetsky
    Nov 9, 2020 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.