Fruit Box is NP-Hard

Added: 2026-05-05

[00:00:00]Okay, yeah, welcome to my talk.

[00:00:03]Thank you for coming. This is Fruit Box is NP-hard.

[00:00:09]Um I will be switching between the slides and other stuff, but uh yeah.

[00:00:17]So, what is Fruit Box?

[00:00:20]Uh it's a web game, and I think you if you might want to play one game right now.

[00:00:28]It's a very simple game. Uh I will send a link in into the the channel.

[00:00:38]It's basically Oh, better turn that off.

[00:00:41]It's this this game where you basically just select numbers that add up to 10.

[00:00:50]This is uh this is the game.

[00:00:53]So, you can start thinking what about this game might be complicated cuz I know when I started playing, I thought it was a really simple game. It's just like a find the correct combination game, and I thought it would be extremely simple to analyze, but it is actually pretty interesting.

[00:01:12]So, yeah, that's >> [snorts] >> you you clear um a rectangular area, and the apples have to sum to 10, and that clears the apples off the board.

[00:01:24]And if you're playing this game, also the you have a time limit, but we don't really care about that for this this talk.

[00:01:34]Uh for this talk, in fact, we will considering infinite Fruit Box where we have infinite area, infinite time, and we don't care about points at all.

[00:01:47]Cuz uh yeah.

[00:01:50]So, let's start with a question like this.

[00:01:55]Can we clear this apple?

[00:01:59]Can I ask everyone here?

[00:02:05]Can this apple be cleared?

[00:02:07]>> a a no to me.

[00:02:10]Oh, oh, you mean not immediately.

[00:02:13]Yes, not immediately. Can it eventually be cleared with >> case, I'll have to think about it.

[00:02:24]Okay, we got a yes.

[00:02:30]Yeah, I think I see it.

[00:02:32]Yeah, so you can uh here I can have the animations. You can uh clear it, but you can also get stuck if you uh clear these two, then these two, then the eight and the two, and then you can clear the seven and the three, but you can also get stuck by doing the nine and the one, and you're immediately out of moves.

[00:02:54]>> [snorts] >> Well, I mean, you can do the seven, the one, and the two if you want, but does you no good for clearing the three.

[00:03:01]So, this is why the game is interesting.

[00:03:06]Cuz it turns out your strategy actually does matter, and you can block yourself off.

[00:03:13]The animations are just OBS recordings.

[00:03:17]Um Okay, so the this is actually Wait, actually let me go back. This is actually the decision problem that I will show as NP-hard that given a a board, is a given apple clearable? This is the question.

[00:03:36]Yes or no, can this apple be cleared?

[00:03:41]Uh no, not all the boards in the game are clearable. In fact, almost none of them are not clearable.

[00:03:49]Uh but I I will talk about that in the second half of the talk. I also played around with building solvers for this game.

[00:03:58]But let's I'll do that later. Okay.

[00:04:03]So, um I don't know how much I have to explain about what NP-hard this is. I'm assuming most people here are pretty familiar, but I will give a quick explanation.

[00:04:16]There's this class of decision problems that are uh in NP, which if you don't know what it means, one way to describe it is their solution is quickly checkable, but that's a very hand-wavy explanation. That's all you're going to get from me right now. And then what um there's also this class of problems that are NP-complete. And when I first learned of this, I thought it was pretty crazy.

[00:04:40]It's basically problems that can be used to solve all the other NP problems.

[00:04:48]Uh which is pretty crazy.

[00:04:51]And one of these NP-complete problems is the Boolean Satisfiability Problem, which uh Also, I will for this talk, I will be assuming that P is not NP. I won't be uh going into that right now. Okay, so the SAT problem is uh basically you're given a Boolean formula, and you have to find variables that satisfy the satisfy it. Is it possible to find uh assignments to the variables, Boolean true or false assignments, that make the whole formula true? And in fact, it turns out it's enough to have that only for um formulas of this form that have uh the variables, the negated variables, then uh ORs, and those combined with ANDs.

[00:05:40]This is the this is called the conjunctive normal form of the formula, and uh yeah, the question is can you find a solution to this? And that's actually an NP-complete problem.

[00:05:53]Okay, is that clear enough?

[00:06:00]I'm with you.

[00:06:03]All right, good.

[00:06:05]Okay, so uh what I will be doing now is going to do a reduction, which I'm going to show that every SAT problem can be turned into a Fruit Box problem like this.

[00:06:17]So, if we had an oracle that could solve every Fruit Box problem, we could use that solution to get a solution for uh the Boolean Satisfiability Problem, which shows that it's at least as hard, so also uh NP-hard.

[00:06:34]Nice.

[00:06:35]Got a we got a 42 in the in the chat.

[00:06:40]Um Yeah, I will I'll be talking more about uh the scores you can get and stuff later on.

[00:06:46]Okay.

[00:06:47]Um Yeah, that's what I'll be showing, and it's going to look something like this.

[00:06:52]I'm going to construct Uh don't worry about this for now. This is just what it's going to look like in the end. I'm going to construct this step by step in a second. It's going to look what's going to look like in the end, a big board, and the question will be can you solve one of these?

[00:07:06]And we're going to construct it from a given formula, and we're going to need a couple of like gadgets for this.

[00:07:13]So, this is how we basically transfer uh a signal. It's like a like a wire.

[00:07:20]So, as you can see, kind of if we can clear the seven, it kind of unlocks this path. We can use this two to clear the eight, and that allows us to clear this path, so we can use the three to clear the seven, and so on. We can have like this redirection. And the nines are just blockers. They're kind of inert cuz the only way to clear a nine is with a one, and I won't be using any other ones, so you can basically just see the nines as blockers.

[00:07:51]And does that make sense?

[00:07:57]Yep.

[00:07:59]Good. I'll move on to how to build an OR gate. So, now we're basically just doing the classic video game building logic gates puzzle. This is if we can clear [clears throat] this eight or we can clear this eight, it allows us to use the three to clear the seven, and we can keep clearing from there on.

[00:08:21]Um similar with the AND gate.

[00:08:27]Can if you can clear both of these, you could clear a seven that's down here somewhere.

[00:08:34]And then the [clears throat] what we actually can't do is build a NOT gate, but turns out we don't need to cuz we have this. This is basically the the most complicated part, which is basically at the start of the game, the player has a choice here. They can use this two to clear this eight or this eight, and I'm going to call one of the paths false, and one of the paths true.

[00:09:00]So, the player has to make a kind of a variable assignment a choice to, and can only unlock stuff in one of these paths.

[00:09:09]Uh and then the we can already move on to the total structure. This is basically what it looks like. This is the uh same formula I had shown as the example.

[00:09:25]Uh yeah, you will you will wire them up separately. So, this is kind of like um circuit diagram here. So, these are the inputs the player basically has to choose.

[00:09:35]Yes.

[00:09:36]The player has to choose um a variable assignment for each of these, and then they can start clearing um down here. So, we use these for redirection, and then it feeds into ORs and ANDs, and then yeah, you can fully see the general structure, and that's basically the whole proof. I'm going to do I'm going to show I have this here.

[00:10:00]Uh we can play. Does anyone want to choose a variable assignment? Wait, let me um Let me go back to the formula.

[00:10:09]This is the same formula as the one shown as an example.

[00:10:16]This one.

[00:10:18]Yeah, this was This was written by uh AI.

[00:10:23]I will show some code by me later. This is uh just uh This was entirely done by AI.

[00:10:30]But yes. Okay, so does anyone want to choose a variable assignment?

[00:10:35]Then we're considering left uh to mean false and right to mean true. And uh this is the formula.

[00:10:54]Uh yeah, there is a reason that everyone has an extra bump. Uh the reason is See, we have two um sevens here, and we want to be able to This is like a branching.

[00:11:03]We want to be able to clear both. Yeah, I'll do it I'll I'll choose a true for C.

[00:11:09]We can clear this one.

[00:11:12]And we can clear this one.

[00:11:15]Okay, uh I'm just going to I I don't quite remember what the correct assignment is. I'm going to choose randomly, and we might get it or you might not.

[00:11:24]So, I'm going to choose some assignments here, and uh Yeah, this already does nothing. So, can see that was a bad strategy if you wanted to clear it.

[00:11:35]So, can get this this or can get this one cleared.

[00:11:46]Uh yeah, we're stuck here.

[00:11:48]Uh we definitely needed this one >> [snorts] >> uh true to get this one.

[00:11:55]So, that was wrong.

[00:11:58]Okay, let's Let me go back to the We'll do it what it looks like if we actually get success.

[00:12:03]Um I need not A B and uh Help me out you guys.

[00:12:18]It looks like you need C, and then D doesn't matter.

[00:12:22]Yeah, okay. So, not A, B, and C.

[00:12:30]Uh like this. Okay, let's try that.

[00:12:36]And then it will be very satisfying, hopefully.

[00:12:41]Uh I don't know if this is too small to read. I have not.

[00:12:49]Can clear this or this one, this or and bam.

[00:12:58]That's it. So, that's basically the proof complete. Um the only if you can if the player can find a variable assignment to these, they can clear it. So, it's basically like the set problem. Okay, yeah, that's the that's the main part of the talk uh done already. The guy The only interesting thing about this really is pretty standard. But the interesting is there's no not gate. And I think I'm I'm pretty sure a not gate is actually impossible.

[00:13:26]Cuz How did I notice this? I don't know.

[00:13:32]I was thinking about uh talks uh topics for a talk. I was going to do fruit box strategies, which I will also do now, but then I came up with maybe I can do something like this that's more uh that's maybe uh better for a a two swap type topic.

[00:13:54]Okay, so there's no not gate. There is something called um the the circuit satisfiability problem, which is basically the same thing, but it's usually phrased with a not gate, which we don't have. And we kind of can't have because being able to clear something does never really makes it impossible to clear something else.

[00:14:17]So, it's kind of weird.

[00:14:21]So, yeah, that's the first part of the talk. And I don't really have uh slides for the second part of the talk.

[00:14:28]But now I'm going to talk about strategies.

[00:14:31]>> Wait a minute.

[00:14:32]>> Any questions? You said Say Say that one more time. Clearing being able to clear something never makes you unable to clear something else. I'm thinking about a case where like you're adding like like 2 + 3 + 2 + 3 or something, and there's nothing else in that row.

[00:14:48]You can clear that, but as soon as you clear one of those four, then you can't clear the rest, right?

[00:14:55]Yeah.

[00:14:57]I'm not sure how to make a not gate out of that or anything.

[00:14:59]>> Yeah, I I I don't know how to prove it, but I feel like it's impossible to make a not gate. Or you can also think about not being able to clear something should make it possible to clear something else. That really seems really difficult to build.

[00:15:13]>> Wasn't that what I Isn't that sort of what that is? If you have like a like a 2 3 2 3, like you can clear the whole row only if you don't clear any individual column.

[00:15:23]If you have 2 3 2 3 in a row, then like if you clear any one of the columns, then you can't clear the whole row.

[00:15:34]Yeah, yeah.

[00:15:35]I I Yeah, I agree, but um yeah, I I I'm not saying I know how to make an a not gate necessarily out of this.

[00:15:43]>> Yeah, I think it's impossible to make a not gate, but I I I don't quite know how to prove that.

[00:15:51]Yeah.

[00:15:54]You can make any not gate true. Yeah.

[00:15:56]Okay.

[00:15:58]So, now I'm going to talk This is actually This has nerd sniped many programmers over the years, actually.

[00:16:04]And if you Google it, you will find a lot of people writing uh programs to solve this.

[00:16:11]Um And I've also written some. It's actually quite difficult cuz a full uh game tree search is basically impossible. There's too many options.

[00:16:22]Um I have uh a chart here with some of the strategies I made.

[00:16:28]Um And also, uh when I started playing, I thought um I thought for sure it wasn't going to be that complicated. And basically, if I have a bot that just never misses anything, it would get most of the way there. It would already be a pretty good strategy. But turns out you actually need to have quite a smart bot to do well in this in this game.

[00:16:50]So, the the first strategy here is just play randomly and do that a bunch of times.

[00:16:59]Like play the game like do pick a random valid move uh repeatedly, make that move until you run out of moves, and then start over from the very start and keep track which your best uh run is. Which your best score is, and then that's the the the thing you'll go with.

[00:17:18]Wait, so you can like reset the board?

[00:17:21]Uh no, you can't reset the board, but since the you never get any information feedback, so you can just do it in your head pretty much.

[00:17:28]>> Oh, okay. Sure, yeah.

[00:17:30]So, you could if you I mean, as a human, it's very hard, but as a computer, you can just imagine what would happen, and um Yep, got you. And I actually I also wrote um I can actually get the the code to move my mouse.

[00:17:49]This is kind of irrelevant, but it's kind of fun.

[00:17:53]Um Wait a second.

[00:18:03]If I it will um It will scan Oh, that's the wrong one.

[00:18:12]Uh Oh, man.

[00:18:30]I think I just started it, and it's going to It's about to move my mouse, which is not what I intended.

[00:18:42]Okay, my stuff moving mouse in a second.

[00:18:44]I'm going to ignore that for now. Okay, so this is the the first way I came up with to play the game, which is randomly. And turns out uh it's actually not very good.

[00:18:57]Um Then the Then I spent a lot of time writing a depth first search, which does a lot better than random, uh but it basically gets stuck in a in a in one opening cuz there's Yeah.

[00:19:17]The cuz of it being depth first, it basically chooses the first few moves, and then wastes all the time uh for the time down the line. So, basically reminiscent of the newest two swap video. At the start, you want to explore, and at the end, you can like calculate all the options.

[00:19:36]Um The the way I simulated this is you play you basically combine the two strategies. You play some random moves at the start, and then you run depth first search from there, and then you repeat that whole thing a couple of times and then pick the best run you got.

[00:19:59]Um Yeah.

[00:20:04]Does that make sense?

[00:20:07]Elliot asks, "What about Monte Carlo tree search?"

[00:20:12]Yeah, well, randomly playing basically is Monte Carlo tree search, right?

[00:20:17]That's what Monte Carlo tree search is, right?

[00:20:22]Um so, it's kind of I don't I think it's different.

[00:20:27]Yeah, how would how would you define it?

[00:20:29]>> I'm not I'm not a I'm not an MCTS expert, but I think the idea is basically >> Neither am I. Neither am I, but >> branches that are already sort of doing well. There's like Yeah, yeah, so you sort of have an exploration feature that explores usually on nodes that are already looking promising.

[00:20:47]Um Yeah. That's That's my understanding.

[00:20:50]>> what I'm what I'm trying to do. I can also there's um Wait, let me find it real quick.

[00:20:57]Um there's also here there's also this thread from 4 years ago where people were talking about the same thing. I only found this after I also spent several days writing solver for this, but um this guy did a competition on the code golf where he uh also let people play this and once people submitted their submissions and he scored them on 10 different boards and gave them points for that.

[00:21:28]And uh the winner of this competition uh I got his code to run. Uh I'm going to I can quickly explain how it works in a second. And this is also on my my chart, which I slightly beat with uh with five move opening plus a huge depth first search plus 100 repetitions, but uh also mine also runs in under 2 minutes. This was the rules for this was the code has to run under 2 minutes, so just like the human you have 2 minutes to solve this. And you do actually run out of time a lot. Like you really wish you had more time.

[00:22:07]Um The way this one works by dingle dooper uh is it's basically just a normal brute force search, but at every step of the game tree you limit yourself to four four options.

[00:22:26]So, um if I uh let me you have like a a game the game tree and you have like 10 options you only pick uh the four uh promising He has a criterion, which is quite important. He chooses four of these and explores each of these four of these, so it's also a it's just a brute force uh search depth first search, but uh he limits the branching to four, so it doesn't quite get stuck too much in uh a deep uh deep lines.

[00:23:09]So, yeah.

[00:23:12]Uh so, that it doesn't explore too much, so you will get over to the other ones.

[00:23:16]And that was the one that won this competition.

[00:23:22]Um yeah. I have an idea for a heuristic that I have a feeling would be kind of good, although I'm >> Yeah. Yeah, I uh I'd be curious to try like um I'm imagining you look at the total set of legal moves immediately, like that are immediately playable, and pick the move that like that maximizes the amount of those greedily one one step in the future.

[00:23:50]Uh maximizes the score greedily or >> No, maximizes the the amount of legal moves.

[00:23:56]Oh, yeah, that's also the actually the first thing I tried to implement, but >> Oh, yeah.

[00:24:00]Yeah, yeah, that was also my first idea.

[00:24:03]It didn't I I don't my code was very messy. I kind of fixed it since then, but so I'm not sure if I maybe it was really bugged, but it didn't work as well as I hoped. Huh.

[00:24:12]>> Uh and and you need some I it could be used as an addition to the other stuff, but you really need some way to throw like more compute at it, like some way to uh do a search or um Yeah, maybe just do that, but then like a depth three search with the same heuristic or something.

[00:24:30]Yeah, you need something like that and uh I I never tried that, so it might be good. What this heuristic is is out of the legal moves you actually want the ones that clear the least apples cuz what you don't want to do is uh what you don't want to do is clear like Let me see if there's a terrible one.

[00:24:50]Uh like this is bad cuz it wastes a lot of small numbers.

[00:24:53]>> Oh, yeah.

[00:24:54]What you want is um like the nines are the ones you really want to get rid of, so these are the nine one moves are good moves. I see. Um and basically any move that only clears two apples, that's a that's a good move. So, that's the heuristic I'm basically using and that also this user was using.

[00:25:13]Um Yeah, you you really don't want to clear a bunch of small numbers. You really want these to be big numbers. And yeah, also someone asked earlier what how many like is it fully clearable? Typically, it's not fully clearable. I mean, it's already not fully clearable if there's more nines than ones, right? Then it's already impossible.

[00:25:33]Uh and that's like half the time, so in I don't know how many are actually solvable cuz I think my solution could still be a lot better, but it feels like only one or two percent or something are solvable.

[00:25:45]Uh like fully clearable.

[00:25:47]There is a YouTube video of someone supposedly fully clearing it as a human, but since it was so difficult for me with the computer, I think it might be it might be fake, but I don't know. Are you guaranteed that all the numbers add up to a multiple of 10?

[00:26:01]I think so. Someone said so.

[00:26:04]Um So, I think they did uh write it so that the the sum is divisible by 10, yeah.

[00:26:12]Yeah, full clears are also would also be NP-hard. And I think there's other questions you could ask.

[00:26:21]Like is a set of moves optimal? That might actually be um more than NP. That might be like PSPACE-hard.

[00:26:30]Uh but I haven't Wait, so do do we have a proof for that that the full clears are also NP-hard or just the individual >> Um I mean, yeah, yeah, yeah. I can I can extend this construction to uh like at the end I can instead of just whoops unlocking the seven, I can build a contraption where this allows you to get a full clear.

[00:26:54]Oh, only if you're able to eliminate the the seven at the bottom.

[00:26:57]>> the seven, [laughter] you can like unlock an ocean of ones that will uh let you clear everything else, so you can full clear if and only if there is a solution for this.

[00:27:08]So, full clears in general are also NP-hard, yeah.

[00:27:19]Um Yeah, what was I talking about anything else before that?

[00:27:29]Pick the move with the most remaining.

[00:27:33]Yeah, I think those might be good.

[00:27:36]But I can't really get it to work that well.

[00:27:39]I that that was my first thought, but I couldn't quite get it to work.

[00:27:44]Um Yeah, I can Let me try to get uh one of my uh um one of my uh programs to run on the board cuz it's kind of fun to watch.

[00:28:16]But yeah, that's that's Elliot, let us know if you end up implementing it. I'm curious to see how that heuristic does at various depths.

[00:28:29]Yeah, I can share my code if um I mean, my code is kind of messy, but um if you want to try to interface with Okay.

[00:28:39]This Okay, let me This kind of bugged out cuz it didn't clear some of them.

[00:28:45]Let me Let's wait for it to be done.

[00:28:51]It plays like this.

[00:28:54]Okay, let me reset.

[00:28:59]We can watch it get a really high score.

[00:29:14]Bam. That's pretty good. Wow. Wait, I'm curious. Before you hit reset, I want to count the number of nines and ones. It looks like Yeah, it looks like there's only one one left and like a lot of nines.

[00:29:24]Uh yeah, although that might not be the total balance cuz sometimes it does use ones like over nines. Like when it does eight one one if at the end you don't really have any other good moves.

[00:29:35]>> Got you.

[00:29:37]Yeah.

[00:29:39]Um Yeah, I can It's fun to watch, so we'll do another one.

[00:29:58]>> Like as a human I got like 127 or something as my personal best. I waste a lot of time playing this game.

[00:30:06]It's quite addictive.

[00:30:08]Quite addictive game.

[00:30:10]Okay, I'm going to have to try it.

[00:30:12]>> [laughter] >> We'll see who can get the highest score in the Okay. in the thread made after this video.

[00:30:19]Yeah, I guess we can end the recording.

[00:30:20]I don't really have anything else to add to the Cool.

[00:30:25]Yeah, I appreciate it. Thank you. Okay.

[00:30:28]Yeah.