Does Ball Sort Puzzle always have a solution?

Question

In this game we have $4$ balls of each colour and $n$ different colours, for a total of $4\times n$ balls, arranged in $n$ stacks. In addition, we have $2$ empty stacks. A maximum of $4$ balls can be in a any stack at a given time. The goal of the game is to sort the balls by colour. Only the top ball of each stack can be moved. A ball can only be left on top of another ball of the same colour or in an empty stack. In the game, $n$ is either $9$ or $12.$ Is this game solvable for any $n$? I guess it is for $n=12$ or lower, but I don't think it is for large $n$. How many empty stacks are needed for it to be solvable for arbitrarily large $n$?

Answer 1

Partial solution: Even for $n = 12$ and $2$ empty stacks, the game is not solvable for this initial configuration:

a a a a b b b b c c c c
d e f g g h i j j k l d
i i k k l l e e f f h h
. . . . . . . . . . . .

This diagram uses $4$ balls of colors a, b, c, spread across the top layers, and $2$ or $3$ balls of colors d, e, f, g, h, i, j, k, l. Each . represents a "don't care" -- i.e. they can be filled arbitrarily with the remaining balls of colors d through l.

The key observation is that the first four moves might as well be all of the same (top) color:

• The first move, without loss of generality, might be a to an empty stack $E_1$.

• Every future move involving an a must be either to $E_1$ or the other empty stack $E_2$, because every a started at the top and it is impossible to put another a on top of it.

• Moving another a to $E_1$ cannot possibly hurt, since nothing else can go onto $E_1$, and the a in $E_1$ cannot go anywhere else (except $E_2$, which doesn't improve the game state).

• Therefore, the first four moves might as well move all four a's onto $E_1$.

Moving all the a's exposed four new balls, but by construction, they are all different colors defg, and, if you move any of them into $E_2$, this exposes yet another new color i or k and the game is at a dead-end (thanks to @JaapScherphuis for pointing this out). The same is true if the first four moves moved all four b's or all four c's. So for the next four moves, we might as well move all four balls of another top color. Another four balls will be exposed. However after these eight moves:

• If we moved all a's and b's, the only common color exposed is g. This is the only legal move left, and whichever g you move, it will expose yet a new color (k or l) and the game is at a dead-end.

• If we moved all a's and c's, the only common color exposed is d, and moving either d will expose a new color (h or i) and the game is at a dead-end.

• If we moved all b's and c's, the only common color exposed is j, and moving either j will expose a new color (e or f) and the game is at a dead-end.

Further thoughts: I wonder if, by similar logic, for any number of empty stacks $m$ (above discusses $m=2$), there exists large enough $n$ s.t. some starting configurations will be unsolvable. All we need is $n$ so large that no matter which $m$ top colors your choose to move first, the $4m$ balls your exposed at layer $3$ have very few common colors, and after making those moves, the newly exposed balls at layer $2$ are all new.

Answer 2

ASSUMPTION : I assume that for each height $1\leqslant h \leqslant 4$, and for each colour $c$, there is a stack where there is a ball of colour $c$ at height $h$.

If we make this assumption about the starting configuration, this game is solvable (although quite boring) for any $n$, and only two empty stacks are needed. Moreover, the number $4$ can be replaced by any number. Here's an algorithm that solves it :

At each depth $d$, we will start with all stacks having the top $d$ balls of the same colour plus two empty stacks, and we will make a permutation of the top $d$ layers, each time moving the top $d$ balls of some full stack to a stack with at least $d$ empty slots. After performing this permutation, we will get all stacks having the top $d+1$ balls of the same colour plus two empty stacks and move to depth $d+1$ until we reach depth 4.

(state 1) Assume we are at depth $d$ with two empty stacks.
Call a stack done if its top $d+1$ balls are of the same colour. If all stacks are done, we can move on to depth $d+1$.

Otherwise there is some stack $s$, say, whose top $d$ balls are of the same colour, but whose next ball is of a different colour. We put these $d$ balls into an empty stack, which we now call storage stack and move to state 2 bellow. The routine bellow will eventually put us in state 1 again, but with at least one stack less that isn't fit for depth $d+1$.

(state 2) We are at depth $d$ except for three distinguished stack :

• one empty stack $E$
• one storage stack (a stack countaining $d$ balls, all of the same colour) $S$
• one incomplete stack $I$

By our assumption above (and since we didn't affect the number of ball of each colour at any height $h$ before), there must be a ball of the same colour as in the storage located at depth $d+1$ in some stack $T$. From now on :

• Either $T \neq I$, we then move the top $d$ balls of $T$ into $E$ (which will becomes the new storage stack) and then move all the balls from $S$ (which becomes empty) into $T$. Notice that $T$ is now done, and that we have hence increased the number of done stacks while returning to state 2.
• If $T = S$, then we put the balls from $S$ into $I$, which is now done, and we reach state 1 again.

Since this process increases the number of sorted stacks, we eventually reach the case $T=S$ above and return to state 1 as claimed. Repeating this process, we eventually reach depth $d+1$.

Conditions on initial configuration are required

@antkam exhibited an initial configuration for which the game is not solvable for $n=12$.

Difficulties seem to arise when there is a big number of balls of the same colour on a given row in the initial configuration. Besides the parameters $m$ and $n$ discused above, let's add a parameter $k$ corresponding to the greatest number of balls allowed in a row of an initial configuration

New question

If one requires $k\leqslant 2$, is there an $m$ such that the game is solvable for all $n$?

Remark For $k=1$ and $m=2$, the game is solvable for all $n$.

A minimal counterexample without the assumption

I claim that the following initial configuration ($n = 12$) can't be solved :

$$\begin{pmatrix} A & A & B & B & C & C & D & D & E & E & F & F \\ G & G & H & H & I & I & J & J & K & K & L & L \\ L & L & K & K & J & J & I & I & H & H & G & G \\ F & F & E & E & D & D & C & C & B & B & A & A\end{pmatrix} $$

---

This section is written by antkam. Very sorry to edit your answer like this!! But I can't fit this into the comments. Feel free to erase or edit further as you like.

Your proposed example is solvable:

A A F F . .
G G L L . .
L L G G . .
F F A A . .

. . . . . .
G G L L . .
L L G G A F
F F A A A F

. . G L . .
. . G L . .
L L G G A F
F F A A A F

. . G L . .
. L G L . F
. L G G A F
. F A A A F

. . G L . F
. . G L . F
L . G G A F
L . A A A F

and the rest is obvious. Now that you solved four colors, and are left with two empty columns, you can iteratively solve each set of four colors.

Answer 3

I think it also quite obvious that the following position for n=12 cannot be solved

a a b b a a b b i i i i
c c c c d d d d j j j j
e e e e f f f f k k k k
g g g g h h h h l l l l

This method also works for n=8 if we just remove the last four stacks.

a a b b a a b b
c c c c d d d d
e e e e f f f f
g g g g h h h h

This position cannot be solved with two empty stacks.

In general the method works for n=4*j with j>=2 just by appending j-2 stacks with the structure

w w w w
x x x x
y y y y
z z z z