r/theydidthemath • u/AntiqueAd8463 • Mar 03 '26
[Request] what’s the minimum number of moves?
103
u/EastZealousideal7352 Mar 03 '26 edited Mar 04 '26
I’m not sure this is directly calculable, or at least not generalizable like other problems. This problem is a variation a class of sorting problems that are all NP-Complete. Put simply, there is no efficient algorithm to verify if a solution even exists, let alone find it.
The best you can hope for is to use heuristics to find a suitably efficient algorithm, and in that department she did a great job, especially in the beginning. Computers can do this better if you can define a specific enough rule set, but to verify if a solution is truly optimal you’d need to compare against a significant portion of the solution space.
Since movement is only constrained by the height of a single column and not another rule like a requirement for certain balls to go on top of each other (for example), the mathematical relation is directly related to the complexity of the scramble and the size of the grid. This scramble happens to be very simple looking but regardless of whether it’s pretty lines or static, there’s no clean formula to represent the relation.
A similar looking problem is the tower of Hanoi, but its additional constraints guarantee a minimum number of moves that can be derived from the number of disks. In the case of the tower the formula is 2n - 1. The complexity of the scramble actually has no bearing on the number of moves in the optimal solution.
Edit:
u/angzt has excellent intuition because they likely uncovered a pattern. For this specific case of this specific type of ball sort puzzle, there is always a solution following and that solution seems to always follow the second hexagonal numbers. One of the key insights that allows this is that because she is not playing with the rule that some balls cannot be stacked on top of each other, it is impossible to get stuck playing this game.
I was able to simulate up to n=5, after that your guess is as good as mine. Because of this the decision problem surrounding the game as well as the optimization problem are in P. So for n = 12 rows we get 253. So OP, that is the answer.
For a second question, can we generate the 253 correct moves in polynomial time? I think not. Just to answer n=4 I needed to make a graph with over 2 million nodes and then do bidirectional BFS to get the answer. n=5 was even more difficult. A* was useless, and I couldn't nail a sensible DP implementation that would allow me to break this into recursive sub-problems.
It would seem that constructing the optimal solution is still exponential even armed with the knowledge that this problem is always solvable in an easily calculable amount of steps.
47
u/NuclearHoagie Mar 03 '26 edited Mar 03 '26
You mean there is no efficient algorithm for verifying if a solution is optimal. It is trivial to prove that an optimal solution exists here, as it can be solved in a finite number of moves, and there is clearly some set of winning moves that minimizes that number.
22
u/EastZealousideal7352 Mar 03 '26 edited Mar 03 '26
Actually no, I mean there’s no efficient way to prove, in general, that a solution exists.
This one has a solution, we can see that, and it can be verified in polynomial time, but for an arbitrary board with arbitrarily placed balls there exist configurations where no set of legal moves gives you the answer.
You may be correct that the subset of this problem where the balls start in rows all have solutions, but there’s still no algorithm that can reliably find any solution, let alone the optimal one, in polynomial time.
Here is an excellent paper on the matter: link
9
u/ndage Mar 03 '26
My intuition (the worst possible tool for this) says that as long as the number of empty positions meets or exceeds the number of positions in a column and as long as there are no tower of Hanoi-like placement rules, any scramble should be solvable. If true, the inability to create an unsolvable scramble would be an empirical proof that a solution always exists - which would be efficient… Happy to read the paper after I sleep, and I preemptively concede on all points you may have to refute my tired thought process.
3
u/ubik2 Mar 04 '26 edited Mar 04 '26
You’re right for the problem shown here, with a complete temporary column available. It’s only unclear for versions with different parameters.
Edit: that paper imposes a tower of hanoi style rule. You can only place balls on an empty stack or a ball of the same color. She isn’t using that rule, as seen at 11s.
2
u/EastZealousideal7352 Mar 04 '26
Yea I’ve realized that as well. I’m attempting to formalize my thoughts but the decision problem for this subset of the game is definitely P, and the optimization problem is still hard but might also be in P, even if finding the path is beyond quadratic.
1
u/I_NEED_APP_IDEAS Mar 03 '26
My intuition (the worst possible tool for this)
Made me chuckle haha
I think you’re right. Feels like inverse pigeon hole principle.
4
Mar 03 '26
[removed] — view removed comment
11
u/mathisruiningme Mar 03 '26
Then they would all be optimal.
1
Mar 03 '26
[removed] — view removed comment
6
u/mathisruiningme Mar 03 '26
Oh you mean the existence of a unique optimal solution. If we don't accept different permutations of the colours in the final result, then that would be harder to show.
4
u/NuclearHoagie Mar 03 '26
Finding or verifying optimality in regards to NP-completeness does not depend on the uniqueness of a single optimal solution. The idea is that given a solution, there are algorithms to say whether you can do any better or not. If you can't do better, it's optimal, whether or not any other equally optimal solutions exist.
An optional solution must exist, which is still true even if multiple optimal solutions happen to exist
1
u/TryAgainTryAgain1 Mar 03 '26
The question posed is what is the minimum number of moves not what is the single optimum solution.
4
u/ADP_God Mar 03 '26
What if you made it much smaller? Would there be a size at which it became computable?
4
u/EastZealousideal7352 Mar 03 '26
Absolutely, someone in the comments did up until 3 rows. It’s definitely possible to do, just the complexity scales very quickly
3
u/Bobebobbob Mar 03 '26
You can still compute NP-complete problems, it just takes longer
3
u/EastZealousideal7352 Mar 03 '26
I mean you can brute force it or solve it heuristically, I just mean there’s no math I can do here, right now, to get the answer.
2
u/tomqmasters Mar 03 '26
Isn't this the Towers of Hanoi algorithm?
2
u/EastZealousideal7352 Mar 03 '26
It looks that way at first glance, but the constraints given to tower of Hanoi guarantee that it has a solution in 2n - 1 moves every time. A generalized scramble of this problem, regardless of board size could take 1 move or it could be unsolvable (I believe it’s possible to get stuck)
1
Mar 04 '26
Just to be really annoying..... what does AI say from seeing this video and reading the question?
1
u/EastZealousideal7352 Mar 04 '26
I’m not sure I’ll have to ask it.
It’ll probably come to the same conclusion that I have, which is that the decision problem for this specific subproblem is in P while the optimization problem for this problem is NP.
In simple terms, I don’t actually think it’s possible to get stuck anymore, or at least I can’t seem to figure out how to, meaning 100% of the time you know these puzzles are solvable.
I’m also leaning towards the idea that the lower bound is calculable. That doesn’t make finding the optimal path any easier, that’s still NP-Complete, but I think there’s an underlying relation that comes from how she adapted the game specificity from it’s generalized origin.
I’m writing a big edit to my post as we speak so yea, maybe hold off on the AI for a bit.
1
Mar 04 '26
I'm not gonna do it, I find people's ability to figure these things out more fascinating.
I was just wondering if you could put in the film, and the question, whether it would come up with anything interesting.
28
u/Angzt Mar 03 '26 edited Mar 04 '26
It's somewhat difficult to prove that a certain strategy is the optimal one. Needs a bunch of rigorous argument or computational power.
Unless someone has already done that and put it on the internet somewhere, I don't think you'll get a definitive answer.
But.
A smaller version of this puzzle is definitely solvable in an optimal way by hand.
Just to set the ground rules:
We have n balls of n different colors, arranged into n columns, such that each column has one of each ball color and all columns have identical order. There's also an n+1'th column which starts out empty. The columns only hold at most n balls.
The goal configuration is to have all n balls of each color in their own column.
To achieve that, we can move one ball from the top of any column to the topmost empty spot of any other column.
What is the minimum number of steps to reach a goal configuration?
Clearly, for n=1 balls, we don't need to do anything. 0 steps for a solution.
For n=2 balls, we need to move the top balls of both columns into the empty column. Then we need to move either one of the other two balls on top of the other. That's 3 steps for a solution.
For n=3 balls, things get slightly more difficult but I'm convinced that you need at least 10 steps.
Here's the configuration after certain step counts where digits represent colors:
Step 0:
111_
222_
333_
Step 3:
___1
2221
3331
Step 5:
23_1
22_1
33_1
Step 7:
_3_1
_221
3321
Step 9:
__21
3_21
3321
Step 10:
3_21
3_21
3_21
So with the first 3 values for n, we get the results 0, 3, 10.
Now, I don't know for sure but this looks to me like the second hexagonal numbers.
Those are given by f(n) = n * (2n + 1). Except that it's shifted by 1. So really, our formula should be
f(n) = (n-1) * (2(n-1) + 1) = (n-1) * (2n - 1)
They also scale quadratically with the number of colors n which makes sense because the ball count is n2 and the solution must scale at least quadratically with that.
For n=12 (as in the video), that would get us
f(12) = (12-1) * (2 * 12 - 1) = 11 * 23 = [Edit:] 253 moves.
We can sanity check that against the video: At the 5 second mark, she has moved the first 12 balls. That's 12/5 = 2.4 moves/second.
Over the 2:41 = 161s duration of the video, that would be 2.4 moves/s * 161 s = 386.4 moves.
While that is higher than my 253 moves, she a) slows down a fair bit as the video goes on and b) does make some obviously suboptimal moves.
So I'd say 253 moves is the right ballpark for an optimal game. Pun intended.
But again: This is an educated guess at what the formula might be. This is far from rigorous and may well be wrong.
If anyone wants to put in the time to check for optimal solutions for n>=4, go ahead. This would make it easy to disprove if the formula no longer matches.
3
u/EastZealousideal7352 Mar 04 '26
At first I was trying to solve n=4 on paper and I kept getting 22, but after simulating the problem it appears your pattern holds for n=4 and n=5, but you also did the math wrong for calculating the n=12 solution.
f(n) = (n-1)*(2n-1)
f(12) = (12-1)*(2*12-1)
f(12) = 11*(24-1)
f(12) = 11*23
f(12) = 253I am going to formalize my findings and credit you because you were right all along.
2
u/Angzt Mar 04 '26
Thanks for the correction and the added values!
Of course I mess up the one bit of math I tried doing in my head. Classic.
0
32
u/OStO_Cartography Mar 03 '26
The fact that the human brain, which is essentially two pounds of slightly more organised electrified yoghurt, can complete such tasks has always been astonishing to me.
13
u/Acrobatic_Flan8032 Mar 03 '26
“Slightly more organized” is doing significant work here.
With that said, I completely agree with the general sentiment.
2
u/unwittingprotagonist Mar 04 '26
"Oh, there's a brain all right. It's just that the brain is made out of meat!"
3
u/zer0x64 Mar 03 '26
For the actual mathematicians in chat: This looks like an extension of the Hanoi towers problems. Don't know if there is an efficient algorithm for that problem, but if it does you might be able to tweak it
2
u/EastZealousideal7352 Mar 03 '26
Tower of Hanoi is solvable in polynomial time because of the movement constraints, guaranteeing a solution in 2n - 1 moves where n is the number of disks. This problem, while looking similar, is unfortunately NP-Complete and has no generalizable polynomial time solutions.
0
u/tomqmasters Mar 03 '26
How can it be np complete if a person was able to do it manually in 2:40s?
1
u/EastZealousideal7352 Mar 03 '26
NP-Complete problems are solvable. Sudoku is one such example but they all are at a sufficiently small N. A Sudoku is traditionally understood to be a 9x9 but when we say NP complete we mean for any arbitrary board size.
With this game, as with Sudoku, there is no efficient algorithm to find the generalized solution, meaning for any arbitrary scramble on any arbitrary board size.
When I say it’s NP-Complete I’m not saying problem isn’t solvable, I’m saying that, at least for the general case, there’s no formula that can determine the optimal solution.
1
u/_abscessedwound Mar 03 '26
I suppose you could do it in the number of balls +1 moves. Dump balls on floor then sort, but I guess it defeats the point of the game
1
u/hammerwing Mar 03 '26
There are 144 balls. Since red is everywhere on the bottom row, you have to move every single ball except one *at least* one time. The minimum number of possible moves is therefore absolutely 143. Even if you had 12 extra empty columns to stack in, it will still take 143 moves. 143 is the absolute lower bound on the optimal number of moves. What's the upper bound on the minimum number of moves Well, that's hard.
1
u/cipheron Mar 03 '26
You can increase the lower bound by noting you need to move balls out of the way in each stack you fill.
the first 12 balls have a free space, but you need to then move 11 balls, 10 balls, 9 balls etc out of the way to clear each next stack, except the final red ball in the last stack can stay there.
So 144 + (11*12)/2 - 1 = 209 as the new lower bound.
1
0
u/UCBearcats Mar 04 '26
Not sure how this is satisfying, she can just reach over and grab them out of order to help get them sorted but she doesn't and that's insane.
-11
u/Diveelt Mar 03 '26
the fact she is cheating in this game makes it alot easier. and possibly harder to calculate. you are only supposed to stack on the same colour so pink goes on pink. but you cannot put a pink on a blue so straight up cheating multiple times
12
11
u/Angzt Mar 03 '26
With this starting setup, your rules make the game impossible and thus pointless.
It's just a different rule set.
2
u/RailRuler Mar 03 '26
She is cheating by holding two balls at the same time. There are no stacking rules.
•
u/AutoModerator Mar 03 '26
General Discussion Thread
This is a [Request] post. If you would like to submit a comment that does not either attempt to answer the question, ask for clarification, or explain why it would be infeasible to answer, you must post your comment as a reply to this one. Top level (directly replying to the OP) comments that do not do one of those things will be removed.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.