Ball-sort transposition

Combinatorial puzzles · Preprint draft

Transposing \(N\) stacks with one spare: the ball-sort puzzle is solved in 55 moves for six colours, and needs at least \((3N^2-N-4)/2\) moves in general

Abstract. Take \(N\) colours, \(N\) balls of each colour, and \(N+1\) stacks of capacity \(N\). At the start one stack is empty and every other stack holds the colours \(1,\dots,N\) from bottom to top. A move takes the top ball of a stack to any stack that is not full. Let \(T(N)\) be the least number of moves after which every stack is empty or holds \(N\) balls of one colour. We prove \(T(N)\ge(3N^2-N-4)/2\) for all \(N\), and we determine \(T(6)=55\) by a computer search; the values \(T(2),\dots,T(5)=3,10,21,36\) were known. For seven colours we obtain \(75\le T(7)\le78\). The search is a breadth-first search pruned by a lower bound \(J\) on the distance to the goal, which we define and prove correct; with \(J\) the proof of \(T(6)\ge55\) visits 4.7 million states. We also give explicit, machine-checked solutions for every \(N\le24\). The exact values agree with \((2N-1)(N-1)\) up to \(N=6\); whether they do for larger \(N\) is open, and the best solutions we know for \(N\ge8\) are longer.

1. Introduction and results

The puzzle is a version of the "ball sort" or "colour sort" games in which a ball may be placed on any ball. There are \(N\) colours, \(N\) balls of each colour and \(N+1\) stacks, which we call lanes, each of capacity \(N\). Lanes are numbered \(0,\dots,N\). In the starting position lane 0 is empty and each of the lanes \(1,\dots,N\) holds the colours \(1,2,\dots,N\) from bottom to top. A move takes the top ball of a non-empty lane and puts it on top of another lane that holds fewer than \(N\) balls. A position is finished if every lane is empty or holds \(N\) balls of one colour. \(T(N)\) is the least number of moves from the starting position to a finished one.

In the starting position every row is monochrome, and in a finished position every column is. The task is to transpose an \(N\times N\) array of stacks using one spare stack.

Theorem 1.

For every \(N\ge2\), \(T(N)\ge(3N^2-N-4)/2\).

Result 2 (computer-assisted).

\(T(6)=55\).

Result 3 (computer-assisted).

\(75\le T(7)\le78\), and for \(8\le N\le24\) the upper bounds of Table 1 hold.

Theorem 1 is proved in Section 4. Result 2 combines an explicit 55-move solution with a search showing that no solution has 54 moves or fewer (Section 6). The upper bounds in Result 3 are explicit move sequences that a short script replays (Section 7).

\(N\)lowerupperlower bound fromupper bound from\((2N-1)(N-1)\)
233exactexhaustive searchoptimal solution3
31010exactexhaustive searchoptimal solution10
42121exactexhaustive searchoptimal solution21
53636exactexhaustive searchoptimal solution36
65555exactpruned search with the bound Jsearch restricted by two rules55
77578openpruned search with the bound Jbeam search78
895106openpruned search with the bound Jearlier recorded solution105
9117140openpruned search with the bound Jbeam search136
10145179openpruned search with the bound Jbeam search171
11175224openpruned search with the bound Jbeam search210
12208272opengeneral bound (3N²−N−4)/2earlier recorded solution253
13245329opengeneral bound (3N²−N−4)/2beam search300
14285387opengeneral bound (3N²−N−4)/2beam search351
15328457opengeneral bound (3N²−N−4)/2beam search406
16374525opengeneral bound (3N²−N−4)/2beam search465
17423625opengeneral bound (3N²−N−4)/2beam search528
18475719opengeneral bound (3N²−N−4)/2beam search595
19530853opengeneral bound (3N²−N−4)/2beam search666
20588992opengeneral bound (3N²−N−4)/2beam search741
216491,114opengeneral bound (3N²−N−4)/2beam search820
227131,355opengeneral bound (3N²−N−4)/2beam search903
237801,568opengeneral bound (3N²−N−4)/2beam search990
248501,672opengeneral bound (3N²−N−4)/2beam search1,081
Table 1. Bounds on \(T(N)\). The last column is the quadratic through the exact values; see Section 9.

Theorem 1 gives \(T(N)\ge1.5N^2-O(N)\). It is known that \(T(N)=O(N^2)\) [1], so \(T(N)=\Theta(N^2)\); the constant is not known.

3. Unmoved balls and homes

Fix a position \(s\) and a sequence of moves from \(s\) to a finished position; we call it the solution. All statements in this section and the next two are about an arbitrary position \(s\), not only the starting one.

In the finished position each colour \(c\) fills one lane, the home of \(c\). Different colours have different homes. A ball is unmoved if the solution never moves it. Let \(M\) be the set of balls that move and \(M_2\) the set of balls that move at least twice. The length of the solution is at least \(|M|+|M_2|\).

For a non-empty lane, its bottom run is the maximal block of equal colours starting at the bottom; \(r\) is its length and \(c_0\) its colour. A lane is uniform if the bottom run is the whole lane, and dirty if there are balls above the bottom run.

Lemma 1.

The unmoved balls of a lane form a block at its bottom. They have one colour, so they are part of the bottom run, and the lane is the home of \(c_0\). Among the lanes with bottom colour \(c\), at most one contains an unmoved ball.

Proof. A ball cannot move before the balls above it, so unmoved balls lie below all moved balls of the lane. Unmoved balls are in the finished position where they are now, and a finished lane has one colour. The last claim holds because \(c\) has one home. ∎

Lemma 2.

A ball of colour \(c\) that moves exactly once moves into the home of \(c\), and at that moment every ball below it in that lane is a ball of colour \(c\) that never moves again.

Proof. After its only move the ball is where it is in the finished position. If a ball below it moved later, it would have to be lifted first. ∎

Lemma 3.

Let \(L\) be a lane of \(s\) that contains a ball which moves. Let \(b\) be the lowest such ball among those present in \(s\), and \(\tau\) the time of the first move of \(b\). Before \(\tau\), no ball that moves exactly once enters \(L\). Immediately after \(\tau\), \(L\) contains only its unmoved balls: if there are any, \(L\) is the home of \(c_0\) and of no other colour; if there are none, \(L\) is empty.

Proof. A ball entering \(L\) before \(\tau\) lies above \(b\) and must leave again before \(b\) moves. At time \(\tau\) everything above \(b\) has left, and below \(b\) there are only unmoved balls. ∎

For a lane as in Lemma 3 we write \(X(L)\) for the balls of \(L\) in \(s\) that move; these are \(b\) and everything above it. The times \(\tau\) of different lanes are times of different moves, so they are distinct.

4. The bound \(h+D\) and the general lower bound

Define \[ h(s)=\sum_{\text{lanes}}(\text{height}-r)\;+\;\sum_{c}\Bigl(\sum_{L:\,c_0(L)=c}r(L)-\max_{L:\,c_0(L)=c}r(L)\Bigr). \] By Lemma 1 the number of unmoved balls of colour \(c\) is at most the largest \(r\) among the lanes with bottom colour \(c\), so \(|M|\ge h(s)\).

Let base be the number of lanes of \(s\) that are empty or uniform. Order the dirty lanes by their times \(\tau\) as \(L_1,L_2,\dots\). When a ball of \(X(L_k)\) makes its first move, the time is at most \(\tau_k\); by Lemmas 2 and 3, if this is its only move, it enters a lane that is empty or uniform in \(s\), or one of \(L_1,\dots,L_{k-1}\). Each lane is the home of at most one colour. Hence the balls of \(X(L_k)\) that move exactly once have at most \(\text{base}+k-1\) different colours, and \[ |M_2\cap X(L_k)|\;\ge\;|X(L_k)|-\sigma_{\text{base}+k-1}\bigl(X(L_k)\bigr), \qquad (1) \] where \(\sigma_j(X)\) is the largest total size of \(j\) colour classes of \(X\). \(X(L_k)\) contains all balls above the bottom run, and it is the whole lane if the lane has no unmoved ball. Adding balls of one colour to a multiset does not decrease the right-hand side of (1). So (1) can be evaluated with \(X\) equal to the part above the bottom run for a lane that keeps its bottom run, and with \(X\) equal to the whole lane otherwise; by Lemma 1 at most one lane per bottom colour keeps.

\(D(s)\) is the minimum of the sum of the right-hand sides of (1) over all orders of the dirty lanes and all admissible choices of the keeping lanes. It is computed by dynamic programming over subsets of the dirty lanes. Since the sets \(X(L_k)\) are disjoint, \(|M_2|\ge D(s)\), and every solution from \(s\) has at least \(h(s)+D(s)\) moves.

Proof of Theorem 1. In the starting position all \(N\) lanes \([1,\dots,N]\) are dirty with \(r=1\) and \(c_0=1\), and base \(=1\). So \(h=N(N-1)+(N-1)=N^2-1\). Every lane contains one ball of each colour, so the lane in position \(k\) contributes \(N-k\) if it does not keep, and \((N-1)-k\) if it is the one keeping lane and \(k\le N-1\). The minimum is \(\sum_{k=1}^{N}(N-k)-1=N(N-1)/2-1\), and \(h+D=(3N^2-N-4)/2\). ∎

5. The bounds \(D'\) and \(J\)

\(D\) lets each lane choose the colours that suit it. In a solution the homes are fixed once. \(D'(s)\) is the minimum, over the same orders, of the cost in which a set \(O\) of open colours is carried along: a lane that keeps opens only its bottom colour \(c_0\) and may keep only if \(c_0\notin O\); a lane that is cleared completely opens one colour of its choice; initially \(O\) is any set of \(\min(\text{base},N)\) colours; the cost of a lane is the number of balls of \(X\) whose colour is not in \(O\). The proof that \(D'(s)\le|M_2|\) follows the solution: with \(R_k\) the set of colours whose home is an empty or uniform lane of \(s\) or one of \(L_1,\dots,L_{k-1}\), Lemmas 2 and 3 give \(|M_2|\ge\sum_k|\{x\in X(L_k):\text{colour}(x)\notin R_k\}|\), and one shows by induction on the number of remaining lanes that the dynamic programme started from any \(O\supseteq R_k\) costs no more. We have \(D'\ge D\).

Two losses remain. \(h\) and \(D'\) are minimised separately, each with its own choice of keeping lanes; and uniform lanes, including lanes that are already finished, are counted as free homes. The bound \(J\) removes both.

Definition.

\(J(s)\) is the minimum cost of the following process. First choose which uniform lanes keep (at most one per colour); their colours are open. For the \(e\) empty lanes choose at most \(e\) further colours to be open. Then clear the dirty lanes and the uniform lanes that do not keep, one at a time, in any order. A dirty lane with \(c_0\) not open may keep: this costs \((\text{height}-r)\) plus the number of balls above the bottom run whose colour is not open, and opens \(c_0\). Any lane may be cleared completely: this costs its height plus the number of its balls whose colour is not open, and then opens one colour that is not open, or none.

Proposition 4.

Every solution from \(s\) has at least \(J(s)\) moves, and \(J\ge h+D'\ge h+D\).

Proof. Take a solution. Uniform lanes with an unmoved ball are the keeping uniform lanes; their colours, and the colours whose home is an empty lane of \(s\), form the initial open set. The other non-empty lanes are ordered by \(\tau\) (Lemma 3 applies to them). Let \(R_k\) be the colours whose home is an empty lane of \(s\), a keeping uniform lane, or one of \(L_1,\dots,L_{k-1}\). By Lemmas 2 and 3 the solution has at least \[ \sum_k\bigl(|X(L_k)|+|\{x\in X(L_k):\text{colour}(x)\notin R_k\}|\bigr) \] moves. This is at least the cost of one run of the process: if \(L_k\) has an unmoved ball it is the home of \(c_0\), so \(c_0\notin R_k\), the process may keep, its cost is at most the solution's because \(X(L_k)\) contains everything above the bottom run, and \(R_{k+1}=R_k\cup\{c_0\}\); if \(L_k\) has no unmoved ball the costs agree, and the process opens the colour whose home is \(L_k\), if there is one. ∎

In the starting position \(J=h+D\), so \(J\) does not improve Theorem 1. It is much sharper in the middle of a solution. On all 37,449,732 states with four colours, \(J\) never exceeds the exact distance, it equals the distance on 13,639,911 states, and the mean difference is 0.92 moves (1.58 for \(h+D'\)).

7. Upper bounds

Each upper bound in Table 1 is a move sequence stored in the repository and replayed by a short script (Section 10). For \(N\le5\) the sequences are optimal. The 55-move solution for \(N=6\) was found by a search restricted by two extra rules (one lane is left untouched until the end, and a ball is only placed on an empty lane or on a ball of the same or a larger colour), under which the search space is small. The 78-move solution for \(N=7\) was found by beam search.

For \(9\le N\le11\) the sequences come from beam search with up to \(10^6\) states per layer, followed by repeated re-solving of the tail of the sequence from intermediate positions; for \(N=9\) and \(N=10\) the pour-based beam search described below (width \(3\cdot10^4\)) later gave 140 and 179, one move fewer each, and for \(N=11\) its parallel reimplementation (width \(10^5\)) gave 224, five fewer. The sequences for \(N=8\) (106 moves) and \(N=12\) (272 moves) are earlier recorded solutions that we have not improved; the latter was found by Claude (Fable) with a beam search whose steps are pours (one ball, the same-colour run on top, or as many balls as fit, moved in one step at a cost equal to the number of balls) and which compares positions at equal move count, with width 2,000. A ball-by-ball beam prunes positions in the middle of a pour because they look worse; comparing only completed pours avoids this. We have no record of the origin of the former. Both replay correctly. The sequences for \(N=13\) (329 moves) and \(N=14\) (387 moves) come from the same pour-based beam search that found the 12-colour solution, with widths \(10^4\) and \(3\cdot10^4\) and different random seeds for breaking ties; they are 35 and 56 moves shorter than our earlier ball-by-ball beam with \(10^6\) states per layer plus re-solving (364 and 443).

For \(15\le N\le24\) we use a construction. Let \(m=\lfloor N/2\rfloor\). Colours \(N,N-1,\dots,\lceil N/2\rceil+1\) are completed one at a time; whenever an empty lane is needed, two lanes are dug down to \([1,\dots,\lceil N/2\rceil]\) and \([1,\dots,m]\) and one is poured onto the other, which gives a lane \([1,\dots,\lceil N/2\rceil,m,\dots,1]\) and an empty lane. What remains is \(m\) such lanes and an empty one. The top layers of these lanes form, after renaming colours, the starting position for \(m\) colours, so a known solution for \(m\) colours can be replayed on them; the rest is solved by beam search. The resulting bounds are roughly \(3.4N^2\) at \(N=24\) and are certainly far from optimal. For \(N=16\), re-solving the tail of the constructed solution with a beam of \(10^6\) states per layer shortened it from 646 to 643 moves; joined with SAT re-solves of 12-move windows earlier in the sequence (646 → 635) at the common position (up to a renaming of lanes) that minimises the total gives 632 moves. Re-solving 32-move windows of that solution with a beam search towards the window's end position (lanes may be renamed; the remaining distance is bounded below by an assignment of lanes) then gave 613 moves. The pour-based beam search with width \(10^4\) independently gave 613 moves, and re-solving its 32-move windows in the same way gave 611; with width \(3\cdot10^4\) it gave 562 moves directly, and re-solving its 48-move windows gave 560. The parallel reimplementation (beam/src/bin/pour.rs) with width \(10^5\) gave 541 moves, and re-solving its 48-move windows gave 538; with re-tuned evaluation weights it gave 525 moves directly. For \(N=17\) the pour-based beam search with width 2,000 gives 715 moves directly, with width \(3\cdot10^4\) 677 moves, and the parallel reimplementation gives 657 moves with width \(10^5\), 650 moves with width \(2\cdot10^5\), and 625 moves with width \(10^5\) and the re-tuned evaluation weights, 118 fewer than the construction (743); for \(N=18\) the parallel reimplementation with width \(10^5\) gives 757 moves, and 719 moves with the re-tuned evaluation weights, against the construction's 863; for \(N=19\) it gives 998 moves (and the parallel reimplementation 900 moves with width \(10^5\), 883 moves with width \(2\cdot10^5\), and 853 moves with width \(10^5\) and the re-tuned evaluation weights) against the construction's 1004, for \(N=20\) the parallel reimplementation with width \(10^5\) gives 1027 moves (992 with the re-tuned evaluation weights) against the construction's 1157, and for \(N=21\) 1302 (1129 with the parallel reimplementation) against 1336; for \(N=22\), \(23\) and \(24\) the parallel reimplementation gives 1355, 1568 and 1672 moves against the construction's 1477, 1632 and 1873. For \(N=15\), checking every window of 12 consecutive moves with a SAT solver (cadical) for a shorter sequence reaching the same position up to a renaming of lanes shortened the constructed solution from 547 to 536 moves; re-solving the tail of the constructed solution with a beam of \(10^6\) states per layer gave 543, and joining the two improvements (they lie in different parts of the sequence) gives 532 moves; re-solving the tail of that solution once more gives 531. The pour-based beam search with width \(3\cdot10^4\) later gave 483 moves directly (best of several random seeds), and re-solving its tail from intermediate positions gave 482. A parallel, memory-lean reimplementation (beam/src/bin/pour.rs) with width \(10^5\) gave 468 moves, and 457 moves with re-tuned evaluation weights (more weight on colour changes and spread, a bonus for an empty lane, and wider random tie-breaking).

8. What the results rely on

Theorem 1 is proved in Section 4 and does not depend on any computation.

The upper bounds depend only on the replay script, which applies the moves to the starting position and tests the final position.

The lower bounds for six and seven colours are computer-assisted. They rely on Proposition 4, on the correctness of our implementation of \(J\), and on the correctness of the search program. The implementation of \(J\) was compared with exact distances on all states for four colours, and a second implementation, written separately in Python, was compared with exact distances on 160,834 states for four and five colours. The search program was run with three different pruning bounds and gave the same conclusions where the runs overlap (Table 2). The search program has not been reimplemented independently, and the proofs in Sections 4 and 5 have not been formally verified.

9. Open questions

The constant. \(1.5\le\liminf T(N)/N^2\), and no explicit small upper constant is known. The exact values satisfy \(T(N)=(2N-1)(N-1)\) for \(2\le N\le6\). For \(N\ge8\) the best solutions we know are longer than this: 106, 140, 179, 224, 272 against 105, 136, 171, 210, 253. These are upper bounds, so they do not refute the formula.

What \(J\) misses. A solution's length is the number of moved balls plus the number of moves that do not take a ball to its final place; call the latter parking moves. In the optimal solutions we examined for \(4\le N\le7\) there are exactly \((N-1)(N-2)\) parking moves: 6, 12, 20, 30. \(J\) certifies 5, 9, 14, 20. The difference comes from balls that are parked more than once (1, 2, 3 and 6 balls move three times in these solutions) and from balls that \(J\) assumes can go straight home. \(J\) counts the balls that must be parked at least once, but it treats parking space as free. In the solutions, when a lane is emptied its balls are parked in the holes left by the colour that was just collected, that is, on top of lanes that will be emptied later; a ball parked on a lane that is emptied before its own colour has a home has to be parked again. A bound that accounts for where parked balls can wait is the natural next step, and we do not have one.

Seven colours. Closing the gap \(75\le T(7)\le78\) by search alone would need tens of thousands of times more states than the last step we ran, at the growth observed so far.

10. Code and data

The repository github.com/wand125/colorsort-transpose contains the move sequences, the bounds with their sources, the search programs, the logs of the deciding runs, and the proofs of Sections 3 to 5 in Japanese. The data page lists the sequences and shows how to check them, and the replay page animates them.

References

  1. M. Szegedy and J. Yu, Rubik Tables and object rearrangement, Int. J. Robotics Research (2022); arXiv:2002.04979.
  2. S. D. Han, N. M. Stiffler, K. E. Bekris and J. Yu, Efficient, high-quality stack rearrangement, IEEE Robotics and Automation Letters 3 (2018), 1608–1615.
  3. Anonymous, web page on matrix transposition with piles, https://piles-five.vercel.app/ (viewed November 2026).
  4. T. Ito et al., Sorting balls and water: equivalence and computational complexity, FUN 2022; arXiv:2202.09495.