# Does Ball Sort Puzzle always have a solution?

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$$?

• @DavidK The meaning of $k$ is defined in the paragraph right abone "Ne'w question" – Olivier Roche Jun 5 '20 at 14:24
• @DavidK Oh, and I'm the one who took the liberty to edit OP and add everything from "Review of OP". – Olivier Roche Jun 5 '20 at 15:33
• @OlivierRoche I see. Funny thing is I looked just about everywhere else for $k.$ Anyway, you can certainly still post your own question. (A link back to this one would be nice.) – David K Jun 5 '20 at 16:37
• Anyway, I found counterexample with $k=2$. I'll edit my answer and cancel my edit. Case closed. – Olivier Roche Jun 5 '20 at 17:04

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.

• Thanks @OlivierRoche - in fact your proof makes me consider how to "maximally" violate your assumption :) and I discovered this after several failed attempt. – antkam Jun 4 '20 at 4:08
• @OlivierRoche - Except one "maximum violation" case - a layer of A on top of a layer of B on top of a layer of C on top of a layer of D, and similarly for other "blocks" of 4 - is easily solvable. :) – antkam Jun 4 '20 at 4:27
• @antkam I think you do need to fill in some more of your "don't care" balls. For example, put ik underneath the ef. This is just to make sure that after removing the four a balls, moving e or f into the last empty column is also a dead end. – Jaap Scherphuis Jun 4 '20 at 9:15
• @OlivierRoche You can put the 4 A balls in the first empty stack. Put two of the B balls on top of the other two Bs. This uncovers two Cs which you can put in the last empty stack. Stack the two Ds, giving you another empty stack. Stack the 4 Bs in the empty stack, and then stack the remaining Cs and Ds. – Jaap Scherphuis Jun 4 '20 at 9:26
• @OlivierRoche - I think Jaap's saying that, a $4\times 4$ block of four colors in four layers, can be solved, starting with $2$ empty columns and leaving $2$ empty columns. Therefore a $4n \times 4$ starting configuration made up of $n$ such $4 \times 4$ blocks, can be solved iteratively one block after another. This is also what I meant by "one maximum violation case (of your assumption) can be easily solved". – antkam Jun 4 '20 at 13:04

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.

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.

• An equivalent assumption is that each layer contains one ball of each color. – David K Jun 5 '20 at 12:29
• @antkam excellent job, I was too quick on the draw! I'll try to see what happens if I permute the intermediate rows a bit, but this time not without a bulletproof proof. :) – Olivier Roche Jun 5 '20 at 20:43