so interesting how I can look at a puzzle from this game after having not played it in years and my eyes still instantly show me the solution for any board smaller than like, 9x9
Hahahahahaha finally a comment I can relate (electrical engineer). Everytime I review a PCB layout I'm like "you could've done it this way, it's shorter!" The bridge Flow Free Bridges is like multi layer boards. Biggest "puzzle" I solved was a 14 layers board (and I got paid doing it)
SAME! I made the realization when I was color coding my nets and I realized I was playing Flow again :) "and getting paid doing it" is right. I've got a lot to learn, I've only done 2 layer boards so far.
I beat every flow game, including the two flow games that aren’t flow free. It took me like 3 years and was a huge meme with my friends because I beat roughly 100k levels, getting all achievements
I've beaten flow free, flow bridges, flow hexes, multiple times each. I'm struggling with the Flow Warps now that I'm getting to the larger packs that have a lot of open edges. I'm glad that there's another extreme Flow fan here!
@@bellama920that’s amazing! The only one I’ve beaten so far is hex’s, but I’m just a few mega levels away from finishing the original game with a star on every level.
There are at least three questions related to Flow, and the one you tackled is "given a set of endpoints, is there a solution?". There's also "given a set of endpoints and the fact that there is a solution, what is the solution?", which is what players are doing, and "find a way to generate valid Flow maps", for which there's almost certainly better options than "guess endpoints, check if there's a solution".
Pretty sure if you can efficiently find a solution provided it exists, you can also efficiently determine whether one exists, so doing it this way should still prove that finding a solution is NP-hard.
When I do most puzzle games of this nature, my process is "given a puzzle, prove there is exactly one solution", which I guess is sort of a combination of the first two (you can't do this without solving), but with a level of rigor (you can't do this by guessing). Flow was very resisilant to this sort of approach, and there were certainly puzzles with multiple solutions, so I wasn't afraid to guess my way through. I started to find, though, that it you added an additional restriction something like "no line may form a 2x2" (a pretty common rule for similar puzzles, it turns out), there did seem to be a solution for these for every puzzle of this sort, which I dubbed "the good solution", and which I assumed were the solution which was central to the generation of the puzzle. Ofc all in concert with stroke minimization like the app wanted for a "perfect" solution. Anyway. Not in any way to take from your three good questions. Just to insist that "what the player is doing" has a little more nuance than brute forcing the puzzle, both in Flow and elsewhere throughout the genre.
@@1vaderNo, since you may have an algorithm which just keeps running, taking polynomial time if there is a solution and not halting when there isn't, solving more and more complex subproblems The full Risch algorithm has some parts which behave like that (and thus require preprocessing)
@jacoblitman4866 Your first two questions are actually sort of "equivalent" from a complexity theoretic point of view. The reason is this: suppose I have a machine that just tells me whether or not a given flow board has a solution. Then what I can do is I can go one color at a time, inputting a possible move, and asking the machine if it's still solvable. If yes, I keep going, if no I backtrack and try a different move. Since any given path only has 4 possible moves at a time (and only 2 or 3 most of the time), in the absolute worst case I would have to consult the machine 4 times for every square on the board, but that's a polynomial number of times. You can play this game with many NP problems, which is why if you look on wikipedia or something, most of the time they'll only talk about the "decision" version of a problem, i.e. just determining "given an input, does a solution exist".
i was starting to think i was the only one playing flow anymore. good to see theres so many other fans out there!! absolutely my favorite mobile game, i love the balance of “must think about this puzzle” and “pattern recognition skills are all i need” great for occupying your brain without tiring it at all
Ok so as a Flow veteran, I had literally beaten every puzzle from every flow game (there are actually 4 official versions from big duck games, flow free is just one of them, plus levels locked behind a pay wall) I have to say, that for humans these puzzles are like you said, absolutely not hard. I LOVED this video, it’s mathy and I’m a nerd. still, the mental algorithm for brute forcing these puzzles is not complicated- there are only a handful of tips like the one given in 2:55 that are needed for solving these puzzles. I encourage you to go play the game on the harder levels, 9x9 or higher for a slightly challenging experience, it’s not mentally draining and super rewarding. Great video!
The Warps version is the Hardest. The puzzles are generally not hard NOW. but as I was going through them, they were definitely hard. Things like Warpway, Large Galaxy, Deep Space and Time Warp still take some thought to solve. Of the weekly puzzles - the Warp Donut is still somewhat difficult. I still play them to go to sleep at night after Years. I can solve the normal version puzzles perfect first time through. But Warps still provides some challenge. (Hexes is the easiest - mathematically provable.)
yea I mean of course puzzles designed for humans to solve aren't going to be that hard, they have an intended solution path thought out by the composer to be rewarding that being said no one knows any algorithm that can solve an arbitrary instance of flow in polynomial time (and if you had one you would get one million dollars as prize)
I'm honestly surprised. Because typically np-complete problems are ones where you have no idea where to start. As in you some things might look right but you always have 0 idea if they are actually part of the solution or not. For this I actually downloaded flow free again briefly, and the first thing I noticed is that all flow free puzzles I've seen (I'm trying the extreme pack) always use all available spaces. So it could be that the subset where the only solution uses every point in the grid isn't actually np-hard like how the general flow puzzle can be.
that, or because the flow game actually only uses very few color dots, so although time complexity is high, 'n' is tiny so we don't feel it. But I feel like it has to be a bit of both. Because not being able to make guaranteed progress at all due to the inability to break them down into independently solvable sub-problems is supposed to be a hallmark of np-hard problems.
I used to play flow free obsessively and its so easy, eventually you can just kinda *see* where everything goes before even drawing any lines, even at the bigger levels. That being said, introduced it to my mom and was astonished to see just how long it took her to solve even the smaller levels and she's a pretty clever person. So it definitely is just a question of experience
Well to be fair being “clever” (depending how you even define that word) doesn’t necessarily have anything to do with your logical reasoning skills. While experience does obviously play a role in literally everything we do, id argue that she probably just doesn’t have very good logic skills. Her intelligence probably shines in other departments, like maybe emotionally or linguistically, etc. But anyone with even just decent logical reasoning probably wont have any problem with flow puzzles even with minimal experience.
It just becomes pattern recognition at a point. Once you’ve seen the same type of puzzle multiple times it just becomes hard coded into your brain. Played too much and now have all perfect levels and am the worm pack wr holder
@@rosiefay7283 what if someone enjoys the relaxing combination of the music and discussion of Flow? >Then they should put both on in seperate tabs Well what if they're in the mobile app?
I've completed every single level in the original game and difficulty is mostly dependant on if there is a line that is incorrect but looks like it could be correct, and size. Great video
I didnt mention it because i didnt want to make the comment to long but i also am about 80% done with bridges and play the daily levels for each game@@NotSomeone68
Such an amazing video from a small channel! I have been playing Flow Free on and off for over 6 years now, people close to me don't seem to know the game but I'm glad there's people out there that still talk about it.
i was a few packs away from 100%ing the free levels, then i lost my phone. then i watch this video and decided to install flow on my new phone and it recovered my cloud data. best day of my life
This is a FANTASTIC video. I am both mesmerized by your lucid explaination of the reduction and clear reasoning/intuition for each step. Hope to see more from you sometime!
In my last year of HS i set it as a goal to finish all the flow games. Finished the original, bridges, hexagons and just as i was 95% done, they released new levels and i finished HS. Cool game, thanks for the video, i might redownload it again!
This video is amazing! My friend sent this to me knowing I am passionate about computational complexity, and this is a great visualization of Flow and the reduction from 3SAT to it!
As someone who has never interacted with complexity theory whatsoever, thank you so much for putting together this video! I feel like I learned a lot. Very interesting concepts well presented, also great choice of music.
Omg this is legit one of my favourite games of all time! So much so that I have a 2796 day streak on the daily puzzles, and I don't think I've missed the weekly challenges since they started either. Such a good little game that's both chill while not being boring, if that makes sense. A good game to play while letting your mind wander 😊
This is a nice video, I enjoyed how it explained the complexity of a game I've never thought it would be that interesting :D Thanks for making this video, because I see the effort put in it
I think you could have mentioned how deciding whether a game is solvable or not related to solving the game: If it is hard to decide if a game is solvable or not, it must be hard to solve the game, even if you know the game is solvable. If a game was easy to solve if you know it is solvable, you could just assume so, try to solve it and return unsat or sat depending on the result
Same as a sudoku. It must be solvable to be a valid sudoku and there are solving techniques which uses that fact. I guess free flow is still NP complete though. But there is a difference between finding out if a solution exists and finding a solution knowing one exists
It does end up being a different question I think. As a long-time Flow Free player, I can vouch that the 5x5 puzzle used in the beginning as an example is pretty easy. From a mathematical perspective - and admittedly I don't know much of anything about complexity theory besides what's in this video - it seems like "difficulty" is measured less by the time it takes and more by whether you have to brute force it. So using the age vs. friends example, finding out people's age is easy because you can ask one by one, but finding pairs of friends is hard because the values depend on other values. Even for a Flow Free puzzle that's "easy" once you know how to play, you're still using "brute force" in that you try/envision certain solutions and then check. You can't ask each square independently what color it's filled with. So I think measuring the difficulty to a player of a given Flow Free level is a different question to the difficulty of knowing if there is a solution, at least in mathematical terms like this. Interesting stuff!
@@timonix2 I am no expert, but I believe the conversion from search to a decision problem and visa versa is always polynomial, you can always just assume that a soduku is solvable, apply your methods and than look at the result
I got my ipod touch Christmas 2012 and played the hell out of flow free for the next couple years of college. Thanks for making such a great video for me personally, very nostalgic, and I love the math. You've earned a new subscriber!
i have all the flow apps and people keep saying they haven’t seen anyone play it in years. thanks for the video dude, we’re both in the right mindset at the right time!
12:30 im sorry but i have no idea how this connects to flow and so i was confused for the entire rest of the video. ive actually done research involving 3SAT so i was excited to see it applied, but it feels like you connected it to a new problem that's distinct from flow
The end of the video makes it a bit clearer. They are at that point using a generalization of the game that is on any graph. (And they represent the graph in a sorta visually initially slightly confusing way)
Exactly!! This doesn’t show Flow is NP complete it shows that “Flow on an arbitrary graph” is NP complete. But that’s not surprising bc the graphs involved in the reduction aren’t even planar.
I waited half of the video to see how specific 3SAT formula and corresponding graph will be transformed into specific flow puzzle. If he can't show it, then how it can be expected for viewers to believe it? Also he did not showed how to perform reverse transformation - from puzzle to 3SAT.
Wow. I learned a bit about this while I was doing my undergrad, but this deep dive on how to do a polynomial reduction was very nicely presented. Well done! The reveal of the non-planar graph of 3SAT was particularly cool.
I'm glad you mentioned Nikoli because I love the pencil puzzle books they publish that have many different types of puzzles. I saw the "Flow" puzzles, which they call NumberLink, and they weren't my favorite. I also played Flow back when it was all the rage, and that was fun. Maybe it's because doing these puzzles with pencil and paper is less fun because of the guessing and checking you sort of have to do sometimes. Some of my other favorites are Nurikabe, Heyawake, and Yajilin. I suspect that most if not all of the puzzles they publish are NP problems. I remember my Combinatorics professor telling us that SlitherLink (another type of Nikoli puzzle) is also NP-complete.
The reason this game is so popular is because on the surface the puzzles seem hard but when you sit down to solve them they are incredibility easy. This makes the user feel smart.
I played a bit of this a few years ago and you're exploring questions that occured to me, thanks. I also played a bit of the version that has some crossover bridges on the grid.
weirdly, got back into the game after many years and also wondered the same thing. glad I'm not the only one to come up with edge strategy, definitely saves me a lot of time solving most puzzles
I made an android app where you can take a screenshot of a flow and it will solve it for you. It works with a bruteforce method (with some optimisations) but it could probably be significantly faster if I implemented the maths behind it as shown in this video (though it already solves 10x10s in under a second)
Didn't play this for years, thought I had a Mandela Effect on my hands til I saw your video. I was certain I used to solve puzzles by having to fill in every cell in an odd manner - version 3. Thank you for the sake of my sanity.
2:45 this is why some of the expert levels are so tricky. The don't have any points on the outer edge. level 7 in the 11 by 11 section of the extreme pack was particularly challenging for me
Maybe I'm remembering wrong, but I played this game in a few versions in the past, all the zigzag versions, and I remember some of them (including the Pou version) weren't premade but rather they randomly generated the puzzles on the fly. I know that is not the same as "checking if it's solvable", it's just creating a solvable one, but it'd be interesting to see a video about that generation process going as indepth as this video did about solvability.
Cool video. I’ve been playing flow free and its variations since it came out in 2012. I’ve completed all puzzles several times. To make the game harder I turn on the option to add the alphabet labels to each dot set and only complete the puzzles by connecting the dots in alphabetical order, only touching each line once.
My favorite variation of this type of game is Piczle Lines DX, where it is similar to version 3 of the Flow game, but the terminal pairs need not have unique colors, and the lengths of the paths between terminals must be exactly a specified length in order for them to link. So, suppose there is a blue terminal with the number 8 on it: that means it can only be connected to another blue terminal that also has the number 8 on it, and only with a path that contains exactly 8 vertices, including the two terminals. Yet, even with this extra restriction, many of the puzzles had multiple valid solutions, either because of the way the paths zigzagged to fill the space, or because four nearby terminals of the same color and path length may be paired in multiple valid ways to fill the space. I always knew it would be really complex to check a puzzle's solution for uniqueness, but this video helped me understand more of what exactly would go into that.
Me, who's Master's project studies NP-Hard algorithm approximations when I click on the video: "I wonder how he's gonna do a reduction from 3SAT to flow" And then that's actually the problem you did the reduction from LOL
god i love flow. i recall it being much more difficult than I find it now, but it wasnt a mind-bogglingly hard game to begin with. glad this vid was recommended to me !!!!!!!!!!
Thanks for the presentation;. I did group theory in uni nearly 50 years ago and don't remember much. I do play Flow Free and on the daily puzzles am currently completed over 2500 days in a row. The warp version in the weekly puzzles can be tricky and some can take me 30 minutes or more to complete.
I wanted to watch a chill video after studying algorithms analysis, P and NP problems, and the night before the test i decide to enjoy this video. What did I find? More talk about P and NP :) Looks good tho, will watch it once im no longer burnt out by this
A problem I've spent a lot of time thinking about is whether there exist two distinct "grid-filling" solutions - every flow puzzle ive played seems to only have one, though I don't know whether this is just because I havent spotted a second, if they are designed that way, or if there's a mathematical proof that two solutions cannot exist. Would be interesting to get an answer
It’s not hard to imagine an example of a puzzle with more than one solution. Imagine a very large grid and only four dots from two colors in the middle. Draw a direct path for one color, and then you can draw a path for the other color that either bypasses the first color on one side or the other.
In case a specific example would be better, imagine a 4x4 grid with the center 4 squares filled with 2 red dots on top and 2 blue dots on the bottom. You can solve this puzzle in at least 3 ways: 50/50 splitting, red looping around blue, or blue looping around red.
@@diggoran sorry, to clarify my specific conjecture was that if a flow problem can only be solved by filling the whole grid (with no "u-turns" like in Version 3), then that solution must be unique. There are lots of counter-examples if you allow one of the solutions to u-turn
I was asked back in high school why I was always playing Flow Free because quote "It wasn't going to get me into college". Which was true, it didn't, but I wish this video came out then so I could prove otherwise. :"^) Thanks for the video, it was a pleasure to tune into~
I've completed all of the puzzles across the several games published in the series. Was so obsessed with solving these at one point I was dreaming about these puzzles
I got this game in 2012. I picked it up again this year and I love it. I have the hexagon version too. 😂 I have decent special memory and something that I’ve noticed is that there are multiple versions of the same patterns in different colours. I’m really glad you mentioned this because my partner was getting really dejected that I can do each puzzle in a few seconds regardless of the size but he who only just started can’t. There are a few permutations that are more or less complex but the versions of the game that have obstacles are by far the most interesting and arguably challenging.
I remember I once tried to code a program that would randomly generate flow puzzles, and I got stuck because I couldn’t figure out how to make the program determine whether a generated puzzle was solvable or not, it’s interesting to see that I got stuck because of really fancy math stuff rather then my own inexperience (I’m used to it being the latter).
I started playing flow my freshman year of high school. Its now 2 and a half years after that and I've completed over 2500 puzzles. Its such a fun game and what interests me the most about it is the multiple ways you can arrive to the same final board state. Starting with different colors or just having different logic. Its such a simple yet fun game. I still hope to beat every level in it one day, but the 900 levels that are mega mania do not interest me. Really enjoyed the video.
Ngl, I really wish that the bit about converting the theoretical, non-planar graph into a planar graph was actually explained. It was screaming at me the whole time, I was like "There's only 3 minutes left, how are they going to explain it???"
I found both satisfiable and not satisfiable 3-sat problems whose graphs are not planar. Instead of proveing that Flow is NP-complete they proved that generalisation of Flow played on arbitrary graphs is NP-complete. I am happy I am not the first who caught that
Just a remark: Maybe it’s questionable to (unintentionally?) pass off the first 19 minutes out of a 20 minute video as your own work (a valid assumption because there’s no attribution anywhere), only to reveal at the end that the mathematics and presentation style came directly from some other publications. What you did is valuable in how you packaged the info and told the story but transparency is necessary. Especially in an era of UA-cam where 90% of STEM channels are plagiarists, you can stand out as having integrity and respect for the field by acknowledging the work of others 🙏🙏 Good luck!!
it's in the description, i think that counts as fair disclosure. youtube is the site you go for repackaged/mediated science communication, not original research (except for those 3 guys that broke the zodiac cipher in a video series that was awesome).
I agree, this is what I don't like about Veritasium's videos; I'm pretty sure that when making the video about p-adic numbers, Derek relied on the video by Eric Rowland, and his visualization of hyperbolic geometry through knitted "rugs" was taken from the Code Parade's channel. Of course, the mentioned authors posted their videos on UA-cam, implying that anyone could access their material without leaving links to the source, but damn, Derek, just show some respect to your colleagues
@@unflexian nowhere in the description does it cite anything at the time of writing this comment, let alone disclosure that he also completely took the presentation style and the historial context section from the aaron adcock et al paper. yeah i know that 90% of STEM channels are clickbait plagiarist garbage. knowing this, a creator can make the conscious choice to not be a bottomfeeder
i have, in fact, played this game for several years now. the first time I played it on my iphone 4 (about 2013). skipped forward to 2018 when the daily puzzle just got added, I played it faithfully. now, at the moment I write this comment, I’ve been playing for 1918 perfect daily streak. after playing for so long, I want to approach the puzzle mathematically, but I am simply too lazy. so technically I was only playing it with my gut feeling up until now. this game accompanied me through the hard & joyful time. I love this game, I hope the dev will not take this game down.
I play a version of this game on the google play store and have beaten over 1,000 levels, lol. The game is still fun. The version I play is called "dot knot" btw and is probably not the best one but I honestly enjoy it because it gets more difficul such that I still get briefly stumped every once in a while. (Play with airplane mode on or wifi off to avoid ads, of course)
We had to make a program to solve larger and larger flow grids for my degree. It was really fun! I think the biggest one i solved was a 10x10, and the prof challenged us to try to get to 12 if we were ambitious. Not sure if anyone achieved that though. I remember implementing a Ford-Fulkerson flow algorithm in such a messy way I lost points for complexity even though it worked well xD
Yooo I’ve been playing flow daily the past few years after so long and everybody’s always like “wtf why do u still play that” it’s nice to see some vids abt flow
I don't think this shows that Flow (the game itself) is NP-complete; it shows that determining if a Flow grid *has* a solution is NP-complete. In the normal play of the game, there is the assumption that a solution exists (as arranged by the setter of the particular grid), and the game play involves finding a/the solution that connects like-coloured cells. This may still be NP-complete, but if it is this video does not prove it. This is more a comment on the wording used in several places about showing that "Flow is NP-complete" which I feel most would assume means "solving a Flow puzzle is NP-complete" rather than the intended meaning of the more difficult "determining if a Flow grid has any solutions"
great video. complexity theory was only a small subsection in my algorithm theory class, but probably the most interesting part. this video gave a very nice refresher on it!
![The moment we stopped understanding AI [AlexNet]](http://i.ytimg.com/vi/UZDiGooFs54/mqdefault.jpg)
so interesting how I can look at a puzzle from this game after having not played it in years and my eyes still instantly show me the solution for any board smaller than like, 9x9
i’m the only one i know that does this, i’m surprised to hear it’s that normal
I like how "3blue1brown style math explainers" are just straight-up a _genre_ on youtube now.
@@w44x ...To be honest, I was wondering how they all have the _exact same_ font effect. Good to know!
@@WackoMcGooseFurthermore, Manim was developed by 3B1B so it really does wrap back around to just being 3B1B style videos.
And I’m all for it
@@w44x Here, there are other similarities than just animations. The tone of the voice and the music are the same as 3B1B.
Just like the "SummoningSalt style dramatic lo-fi speedrun history" videos
This game indirectly trained me in a way that is quite easy and enjoyable for me to draw PCB tracks when I'm designing
Same! Lol. That and Satisfactory have helped me in my PCB layout skills
Hahahahahaha finally a comment I can relate (electrical engineer). Everytime I review a PCB layout I'm like "you could've done it this way, it's shorter!" The bridge Flow Free Bridges is like multi layer boards. Biggest "puzzle" I solved was a 14 layers board (and I got paid doing it)
@@phiIippejean 14 LAYERS? What were you working on? I think the most layers any board at my company has is 8 or 10
Ahah, I found it to late, It could I save so many hours of my life wasted on kicad
SAME! I made the realization when I was color coding my nets and I realized I was playing Flow again :) "and getting paid doing it" is right.
I've got a lot to learn, I've only done 2 layer boards so far.
I beat every flow game, including the two flow games that aren’t flow free. It took me like 3 years and was a huge meme with my friends because I beat roughly 100k levels, getting all achievements
100k levels?????
Damm
I've beaten flow free, flow bridges, flow hexes, multiple times each. I'm struggling with the Flow Warps now that I'm getting to the larger packs that have a lot of open edges. I'm glad that there's another extreme Flow fan here!
@@bellama920that’s amazing! The only one I’ve beaten so far is hex’s, but I’m just a few mega levels away from finishing the original game with a star on every level.
I'm working slowly through 100%ing bridges perfectly- so far I'm on the 4th game pack, but I only play it when I'm *really* bored, haha
There are at least three questions related to Flow, and the one you tackled is "given a set of endpoints, is there a solution?". There's also "given a set of endpoints and the fact that there is a solution, what is the solution?", which is what players are doing, and "find a way to generate valid Flow maps", for which there's almost certainly better options than "guess endpoints, check if there's a solution".
Great point, I almost missed that. On another note, do you think solving any of the versions of Flow given a solution exists is polynomial-time?
Pretty sure if you can efficiently find a solution provided it exists, you can also efficiently determine whether one exists, so doing it this way should still prove that finding a solution is NP-hard.
When I do most puzzle games of this nature, my process is "given a puzzle, prove there is exactly one solution", which I guess is sort of a combination of the first two (you can't do this without solving), but with a level of rigor (you can't do this by guessing). Flow was very resisilant to this sort of approach, and there were certainly puzzles with multiple solutions, so I wasn't afraid to guess my way through. I started to find, though, that it you added an additional restriction something like "no line may form a 2x2" (a pretty common rule for similar puzzles, it turns out), there did seem to be a solution for these for every puzzle of this sort, which I dubbed "the good solution", and which I assumed were the solution which was central to the generation of the puzzle. Ofc all in concert with stroke minimization like the app wanted for a "perfect" solution.
Anyway. Not in any way to take from your three good questions. Just to insist that "what the player is doing" has a little more nuance than brute forcing the puzzle, both in Flow and elsewhere throughout the genre.
@@1vaderNo, since you may have an algorithm which just keeps running, taking polynomial time if there is a solution and not halting when there isn't, solving more and more complex subproblems
The full Risch algorithm has some parts which behave like that (and thus require preprocessing)
@jacoblitman4866 Your first two questions are actually sort of "equivalent" from a complexity theoretic point of view. The reason is this: suppose I have a machine that just tells me whether or not a given flow board has a solution. Then what I can do is I can go one color at a time, inputting a possible move, and asking the machine if it's still solvable. If yes, I keep going, if no I backtrack and try a different move. Since any given path only has 4 possible moves at a time (and only 2 or 3 most of the time), in the absolute worst case I would have to consult the machine 4 times for every square on the board, but that's a polynomial number of times.
You can play this game with many NP problems, which is why if you look on wikipedia or something, most of the time they'll only talk about the "decision" version of a problem, i.e. just determining "given an input, does a solution exist".
I've played this quite a bit over the years and it's nice to see it intersect with complexity theory. Great video, glad it got recommended.
Please check out Mathematichess.
les jumpscare
nice
@@mattbatwingsglad to see your a fan of flow
i was starting to think i was the only one playing flow anymore. good to see theres so many other fans out there!! absolutely my favorite mobile game, i love the balance of “must think about this puzzle” and “pattern recognition skills are all i need” great for occupying your brain without tiring it at all
Ok so as a Flow veteran, I had literally beaten every puzzle from every flow game (there are actually 4 official versions from big duck games, flow free is just one of them, plus levels locked behind a pay wall) I have to say, that for humans these puzzles are like you said, absolutely not hard. I LOVED this video, it’s mathy and I’m a nerd. still, the mental algorithm for brute forcing these puzzles is not complicated- there are only a handful of tips like the one given in 2:55 that are needed for solving these puzzles. I encourage you to go play the game on the harder levels, 9x9 or higher for a slightly challenging experience, it’s not mentally draining and super rewarding. Great video!
The Warps version is the Hardest. The puzzles are generally not hard NOW. but as I was going through them, they were definitely hard. Things like Warpway, Large Galaxy, Deep Space and Time Warp still take some thought to solve. Of the weekly puzzles - the Warp Donut is still somewhat difficult. I still play them to go to sleep at night after Years. I can solve the normal version puzzles perfect first time through. But Warps still provides some challenge. (Hexes is the easiest - mathematically provable.)
yea I mean of course puzzles designed for humans to solve aren't going to be that hard, they have an intended solution path thought out by the composer to be rewarding
that being said no one knows any algorithm that can solve an arbitrary instance of flow in polynomial time (and if you had one you would get one million dollars as prize)
I'm honestly surprised. Because typically np-complete problems are ones where you have no idea where to start. As in you some things might look right but you always have 0 idea if they are actually part of the solution or not.
For this I actually downloaded flow free again briefly, and the first thing I noticed is that all flow free puzzles I've seen (I'm trying the extreme pack) always use all available spaces. So it could be that the subset where the only solution uses every point in the grid isn't actually np-hard like how the general flow puzzle can be.
that, or because the flow game actually only uses very few color dots, so although time complexity is high, 'n' is tiny so we don't feel it.
But I feel like it has to be a bit of both. Because not being able to make guaranteed progress at all due to the inability to break them down into independently solvable sub-problems is supposed to be a hallmark of np-hard problems.
There's also a Flow Sudoku, but playing that felt more annoying as opposed to the satisfying difficulty of Warps.
I used to play flow free obsessively and its so easy, eventually you can just kinda *see* where everything goes before even drawing any lines, even at the bigger levels. That being said, introduced it to my mom and was astonished to see just how long it took her to solve even the smaller levels and she's a pretty clever person. So it definitely is just a question of experience
Well to be fair being “clever” (depending how you even define that word) doesn’t necessarily have anything to do with your logical reasoning skills. While experience does obviously play a role in literally everything we do, id argue that she probably just doesn’t have very good logic skills. Her intelligence probably shines in other departments, like maybe emotionally or linguistically, etc.
But anyone with even just decent logical reasoning probably wont have any problem with flow puzzles even with minimal experience.
It just becomes pattern recognition at a point. Once you’ve seen the same type of puzzle multiple times it just becomes hard coded into your brain. Played too much and now have all perfect levels and am the worm pack wr holder
Great video but the music makes me feel like I’m watching a documentary about a recent tragedy
I would like to say that I enjoy the music as someone who enjoys these videos as sleep aid. To me it's not sad but relaxing and somewhat nostalgic.
it's satie-esque and complements the drama of the concepts
@@astrocoastalprocessorsatie? The composer?
If anyone finds the music relaxing, that's great, but then the music and the discussion of Flow should be in *separate* videos.
@@rosiefay7283 what if someone enjoys the relaxing combination of the music and discussion of Flow?
>Then they should put both on in seperate tabs
Well what if they're in the mobile app?
Y'know, I never expected to come across a video going so in-depth about Flow. I always just thought, "Connect dots, win game."
I love that these 3B1B style videos are trending now. Always learning something new
Those summer of math events really helped a lot with this, it's been great
@@user-ls4bl2sf1d 3 blue 1 brown
@@user-ls4bl2sf1d 3blue1brown, a channel on youtube
@@user-ls4bl2sf1d ua-cam.com/users/3blue1brown
@@user-ls4bl2sf1d 3b1b is the youtube channel 3Blue1Brown
Well, wasn’t expecting a Flow Free essay video to be on my 2024 bingo board. Well-thought out video, by the way.
I've completed every single level in the original game and difficulty is mostly dependant on if there is a line that is incorrect but looks like it could be correct, and size. Great video
Try the Bridges (harder) or the Warps (hardest) versions of the game. Hexes is kind of boring - being much easier once you catch on.
I didnt mention it because i didnt want to make the comment to long but i also am about 80% done with bridges and play the daily levels for each game@@NotSomeone68
@@NotSomeone68 hexes to me is harder but just at the biggest level
Flow free has had a permanent Tetris effect on my brain I’m excited to watch this
The music credits are incorrect, the music that plays throughout this video is not "Filaments" by Scott Buckley.
Yeah, I’ve been looking for the real song for a while but can’t find it. Please let me know if you find anything!
The sound effects are without a doubt the best part of flow
Is this a joke?
Such an amazing video from a small channel! I have been playing Flow Free on and off for over 6 years now, people close to me don't seem to know the game but I'm glad there's people out there that still talk about it.
I remember playing this game when I was very young. Brings back memories.
same
i was a few packs away from 100%ing the free levels, then i lost my phone.
then i watch this video and decided to install flow on my new phone and it recovered my cloud data.
best day of my life
This video reminded me that I needed to do my daily flow puzzle. Thank you. 17 day streak so far.
This is a FANTASTIC video. I am both mesmerized by your lucid explaination of the reduction and clear reasoning/intuition for each step. Hope to see more from you sometime!
In my last year of HS i set it as a goal to finish all the flow games. Finished the original, bridges, hexagons and just as i was 95% done, they released new levels and i finished HS. Cool game, thanks for the video, i might redownload it again!
one thing I love abt them is how they do keep updating the game! It’s oddly still alive for such an old app
This video is amazing! My friend sent this to me knowing I am passionate about computational complexity, and this is a great visualization of Flow and the reduction from 3SAT to it!
This was basically the last section of my intro to algorithms cs class in university. Good refresher.
seeing this on my utube explore page was one of the happiest moments of my life. im so glad this game is getting more attention
As someone who has never interacted with complexity theory whatsoever, thank you so much for putting together this video! I feel like I learned a lot. Very interesting concepts well presented, also great choice of music.
Omg this is legit one of my favourite games of all time! So much so that I have a 2796 day streak on the daily puzzles, and I don't think I've missed the weekly challenges since they started either. Such a good little game that's both chill while not being boring, if that makes sense. A good game to play while letting your mind wander 😊
This is a nice video, I enjoyed how it explained the complexity of a game I've never thought it would be that interesting :D
Thanks for making this video, because I see the effort put in it
Sometimes, figuring out one line makes everything else literally fall neatly in your lap.
I think you could have mentioned how deciding whether a game is solvable or not related to solving the game: If it is hard to decide if a game is solvable or not, it must be hard to solve the game, even if you know the game is solvable. If a game was easy to solve if you know it is solvable, you could just assume so, try to solve it and return unsat or sat depending on the result
Same as a sudoku. It must be solvable to be a valid sudoku and there are solving techniques which uses that fact. I guess free flow is still NP complete though. But there is a difference between finding out if a solution exists and finding a solution knowing one exists
It does end up being a different question I think. As a long-time Flow Free player, I can vouch that the 5x5 puzzle used in the beginning as an example is pretty easy. From a mathematical perspective - and admittedly I don't know much of anything about complexity theory besides what's in this video - it seems like "difficulty" is measured less by the time it takes and more by whether you have to brute force it. So using the age vs. friends example, finding out people's age is easy because you can ask one by one, but finding pairs of friends is hard because the values depend on other values. Even for a Flow Free puzzle that's "easy" once you know how to play, you're still using "brute force" in that you try/envision certain solutions and then check. You can't ask each square independently what color it's filled with. So I think measuring the difficulty to a player of a given Flow Free level is a different question to the difficulty of knowing if there is a solution, at least in mathematical terms like this. Interesting stuff!
@@larsatticus6807 Complexity is less about the time required to solve an instance of a problem and more about how the problem scales with size
@@timonix2 I am no expert, but I believe the conversion from search to a decision problem and visa versa is always polynomial, you can always just assume that a soduku is solvable, apply your methods and than look at the result
@@martinclever342 Ooh, that makes sense! Thank you!
I got my ipod touch Christmas 2012 and played the hell out of flow free for the next couple years of college. Thanks for making such a great video for me personally, very nostalgic, and I love the math. You've earned a new subscriber!
i have all the flow apps and people keep saying they haven’t seen anyone play it in years. thanks for the video dude, we’re both in the right mindset at the right time!
my favorite past-time video game has been mentioned! I am deeply grateful
12:30 im sorry but i have no idea how this connects to flow and so i was confused for the entire rest of the video. ive actually done research involving 3SAT so i was excited to see it applied, but it feels like you connected it to a new problem that's distinct from flow
The end of the video makes it a bit clearer. They are at that point using a generalization of the game that is on any graph. (And they represent the graph in a sorta visually initially slightly confusing way)
Exactly!! This doesn’t show Flow is NP complete it shows that “Flow on an arbitrary graph” is NP complete. But that’s not surprising bc the graphs involved in the reduction aren’t even planar.
I waited half of the video to see how specific 3SAT formula and corresponding graph will be transformed into specific flow puzzle.
If he can't show it, then how it can be expected for viewers to believe it?
Also he did not showed how to perform reverse transformation - from puzzle to 3SAT.
Glad to hear someone else in the world plays this game. For years I looked online for some kind of community, but it was like the game didn't exist.
Wow. I learned a bit about this while I was doing my undergrad, but this deep dive on how to do a polynomial reduction was very nicely presented. Well done! The reveal of the non-planar graph of 3SAT was particularly cool.
I'm glad you mentioned Nikoli because I love the pencil puzzle books they publish that have many different types of puzzles. I saw the "Flow" puzzles, which they call NumberLink, and they weren't my favorite. I also played Flow back when it was all the rage, and that was fun. Maybe it's because doing these puzzles with pencil and paper is less fun because of the guessing and checking you sort of have to do sometimes. Some of my other favorites are Nurikabe, Heyawake, and Yajilin. I suspect that most if not all of the puzzles they publish are NP problems. I remember my Combinatorics professor telling us that SlitherLink (another type of Nikoli puzzle) is also NP-complete.
Crazy how you dropped the most well made video on UA-cam about flow free
The reason this game is so popular is because on the surface the puzzles seem hard but when you sit down to solve them they are incredibility easy. This makes the user feel smart.
I played a bit of this a few years ago and you're exploring questions that occured to me, thanks.
I also played a bit of the version that has some crossover bridges on the grid.
Omg this speaks to me. Had this app forever but now again getting into it
Flow really brings back memories. Guess I need to redownload it now
weirdly, got back into the game after many years and also wondered the same thing. glad I'm not the only one to come up with edge strategy, definitely saves me a lot of time solving most puzzles
finally. A video on my recommended that is literally FOR me. me and my daily streak and hundreds of hours put into these little app games . Amazing
I made an android app where you can take a screenshot of a flow and it will solve it for you. It works with a bruteforce method (with some optimisations) but it could probably be significantly faster if I implemented the maths behind it as shown in this video (though it already solves 10x10s in under a second)
Didn't play this for years, thought I had a Mandela Effect on my hands til I saw your video. I was certain I used to solve puzzles by having to fill in every cell in an odd manner - version 3. Thank you for the sake of my sanity.
2:45 this is why some of the expert levels are so tricky. The don't have any points on the outer edge. level 7 in the 11 by 11 section of the extreme pack was particularly challenging for me
Maybe I'm remembering wrong, but I played this game in a few versions in the past, all the zigzag versions, and I remember some of them (including the Pou version) weren't premade but rather they randomly generated the puzzles on the fly. I know that is not the same as "checking if it's solvable", it's just creating a solvable one, but it'd be interesting to see a video about that generation process going as indepth as this video did about solvability.
I played it so much that I was constantly waiting on new packs. Great memories
This is the first time that I actually had fun with a reduction proof! Very nice!
I knew I remembered this game! The moment I saw the thumbnail, I immediately downloaded it out of nostalgia but to also rewire my brain.
You just revitalized a core memory, thanks
Cool video. I’ve been playing flow free and its variations since it came out in 2012. I’ve completed all puzzles several times.
To make the game harder I turn on the option to add the alphabet labels to each dot set and only complete the puzzles by connecting the dots in alphabetical order, only touching each line once.
Ooh, that's a really cool idea!
Love when youtubers randomly give me a load of nostalgia
My favorite variation of this type of game is Piczle Lines DX, where it is similar to version 3 of the Flow game, but the terminal pairs need not have unique colors, and the lengths of the paths between terminals must be exactly a specified length in order for them to link. So, suppose there is a blue terminal with the number 8 on it: that means it can only be connected to another blue terminal that also has the number 8 on it, and only with a path that contains exactly 8 vertices, including the two terminals. Yet, even with this extra restriction, many of the puzzles had multiple valid solutions, either because of the way the paths zigzagged to fill the space, or because four nearby terminals of the same color and path length may be paired in multiple valid ways to fill the space. I always knew it would be really complex to check a puzzle's solution for uniqueness, but this video helped me understand more of what exactly would go into that.
Yoooooooo its the game that carried my childhood!
Me, who's Master's project studies NP-Hard algorithm approximations when I click on the video:
"I wonder how he's gonna do a reduction from 3SAT to flow"
And then that's actually the problem you did the reduction from LOL
god i love flow. i recall it being much more difficult than I find it now, but it wasnt a mind-bogglingly hard game to begin with. glad this vid was recommended to me !!!!!!!!!!
I had the same idea when I played flow and learned about complexity theory, but didn't have the will to prove it. Thank you so much!
I used to love this game. I might download it and play again becausde i miss it so much
Thanks for the presentation;. I did group theory in uni nearly 50 years ago and don't remember much. I do play Flow Free and on the daily puzzles am currently completed over 2500 days in a row. The warp version in the weekly puzzles can be tricky and some can take me 30 minutes or more to complete.
I wanted to watch a chill video after studying algorithms analysis, P and NP problems, and the night before the test i decide to enjoy this video. What did I find? More talk about P and NP :)
Looks good tho, will watch it once im no longer burnt out by this
The background music makes this borderline asmr
i literally opened youtube to find something to put on while playing flow, and then i saw this recommended hahaha. looking forward to it!
i have taken complexity theory in university and i love this video! well done, super interesting, love the theory behind it
Back in the day I was going strong with this game and the spin offs! I want to go back to it tho
A problem I've spent a lot of time thinking about is whether there exist two distinct "grid-filling" solutions - every flow puzzle ive played seems to only have one, though I don't know whether this is just because I havent spotted a second, if they are designed that way, or if there's a mathematical proof that two solutions cannot exist. Would be interesting to get an answer
It’s not hard to imagine an example of a puzzle with more than one solution. Imagine a very large grid and only four dots from two colors in the middle. Draw a direct path for one color, and then you can draw a path for the other color that either bypasses the first color on one side or the other.
In case a specific example would be better, imagine a 4x4 grid with the center 4 squares filled with 2 red dots on top and 2 blue dots on the bottom. You can solve this puzzle in at least 3 ways: 50/50 splitting, red looping around blue, or blue looping around red.
@@diggoran sorry, to clarify my specific conjecture was that if a flow problem can only be solved by filling the whole grid (with no "u-turns" like in Version 3), then that solution must be unique. There are lots of counter-examples if you allow one of the solutions to u-turn
7 minutes in and I wish I had this video while I was in university. Good job explaining P, NP and NP-complete.
🎀 I don't understand a word of this video, but I'm glad it exists
This game was a fun time passer back in the day. This was a good walk down memory lane
I was asked back in high school why I was always playing Flow Free because quote "It wasn't going to get me into college". Which was true, it didn't, but I wish this video came out then so I could prove otherwise. :"^) Thanks for the video, it was a pleasure to tune into~
This video gives me flashbacks to comp sci. Incredible work
What a great video, thank you
0:44 not me taking screenshots of puzzles and solving them
I am currently playing this game as this video was recommended to me, perfect way to get my attention
I've completed all of the puzzles across the several games published in the series. Was so obsessed with solving these at one point I was dreaming about these puzzles
I got this game in 2012. I picked it up again this year and I love it. I have the hexagon version too. 😂 I have decent special memory and something that I’ve noticed is that there are multiple versions of the same patterns in different colours. I’m really glad you mentioned this because my partner was getting really dejected that I can do each puzzle in a few seconds regardless of the size but he who only just started can’t.
There are a few permutations that are more or less complex but the versions of the game that have obstacles are by far the most interesting and arguably challenging.
so trippy seeing this game again, I played loads of it as a kid and didn't know anybody else in the world knew about it
I remember I once tried to code a program that would randomly generate flow puzzles, and I got stuck because I couldn’t figure out how to make the program determine whether a generated puzzle was solvable or not, it’s interesting to see that I got stuck because of really fancy math stuff rather then my own inexperience (I’m used to it being the latter).
i havent thought about this game in 10 years, thank you for reminding me of its existence
I started playing flow my freshman year of high school. Its now 2 and a half years after that and I've completed over 2500 puzzles. Its such a fun game and what interests me the most about it is the multiple ways you can arrive to the same final board state. Starting with different colors or just having different logic. Its such a simple yet fun game. I still hope to beat every level in it one day, but the 900 levels that are mega mania do not interest me. Really enjoyed the video.
Intriguing and well made, I can’t wait to see more!
This was so much more than a video about Flow! Fantastic work!!
I have done so many levels in this game it’s absorbed so many years of my life
Ngl, I really wish that the bit about converting the theoretical, non-planar graph into a planar graph was actually explained. It was screaming at me the whole time, I was like "There's only 3 minutes left, how are they going to explain it???"
I found both satisfiable and not satisfiable 3-sat problems whose graphs are not planar. Instead of proveing that Flow is NP-complete they proved that generalisation of Flow played on arbitrary graphs is NP-complete. I am happy I am not the first who caught that
Just a remark: Maybe it’s questionable to (unintentionally?) pass off the first 19 minutes out of a 20 minute video as your own work (a valid assumption because there’s no attribution anywhere), only to reveal at the end that the mathematics and presentation style came directly from some other publications. What you did is valuable in how you packaged the info and told the story but transparency is necessary. Especially in an era of UA-cam where 90% of STEM channels are plagiarists, you can stand out as having integrity and respect for the field by acknowledging the work of others 🙏🙏
Good luck!!
it's in the description, i think that counts as fair disclosure. youtube is the site you go for repackaged/mediated science communication, not original research (except for those 3 guys that broke the zodiac cipher in a video series that was awesome).
@@unflexian where in the description is it?
I agree, this is what I don't like about Veritasium's videos; I'm pretty sure that when making the video about p-adic numbers, Derek relied on the video by Eric Rowland, and his visualization of hyperbolic geometry through knitted "rugs" was taken from the Code Parade's channel. Of course, the mentioned authors posted their videos on UA-cam, implying that anyone could access their material without leaving links to the source, but damn, Derek, just show some respect to your colleagues
@@unflexianwhere in the description ? I could not find it
@@unflexian nowhere in the description does it cite anything at the time of writing this comment, let alone disclosure that he also completely took the presentation style and the historial context section from the aaron adcock et al paper.
yeah i know that 90% of STEM channels are clickbait plagiarist garbage. knowing this, a creator can make the conscious choice to not be a bottomfeeder
this video just unlocked a core memory
i have, in fact, played this game for several years now. the first time I played it on my iphone 4 (about 2013). skipped forward to 2018 when the daily puzzle just got added, I played it faithfully. now, at the moment I write this comment, I’ve been playing for 1918 perfect daily streak. after playing for so long, I want to approach the puzzle mathematically, but I am simply too lazy. so technically I was only playing it with my gut feeling up until now. this game accompanied me through the hard & joyful time. I love this game, I hope the dev will not take this game down.
As a math nerd who's obsessed with Flow Free , this video checks all my boxes
I play a version of this game on the google play store and have beaten over 1,000 levels, lol. The game is still fun.
The version I play is called "dot knot" btw and is probably not the best one but I honestly enjoy it because it gets more difficul such that I still get briefly stumped every once in a while. (Play with airplane mode on or wifi off to avoid ads, of course)
What are the chances that I find a UA-cam video on the exact same topic as my senior thesis in high school
I play a game called "Puzzledom" which includes so many puzzles and those nikoli games.
We had to make a program to solve larger and larger flow grids for my degree. It was really fun! I think the biggest one i solved was a 10x10, and the prof challenged us to try to get to 12 if we were ambitious. Not sure if anyone achieved that though. I remember implementing a Ford-Fulkerson flow algorithm in such a messy way I lost points for complexity even though it worked well xD
Yooo I’ve been playing flow daily the past few years after so long and everybody’s always like “wtf why do u still play that” it’s nice to see some vids abt flow
I feel like an og because I had the game when it came out when I was like 7 but for whatever reason it is suddenly more popular than ever
It is so damn cool to see manim being used so widely for videos like this. Grant from 3b1b is such a gamechanger.
I don't think this shows that Flow (the game itself) is NP-complete; it shows that determining if a Flow grid *has* a solution is NP-complete.
In the normal play of the game, there is the assumption that a solution exists (as arranged by the setter of the particular grid), and the game play involves finding a/the solution that connects like-coloured cells. This may still be NP-complete, but if it is this video does not prove it.
This is more a comment on the wording used in several places about showing that "Flow is NP-complete" which I feel most would assume means "solving a Flow puzzle is NP-complete" rather than the intended meaning of the more difficult "determining if a Flow grid has any solutions"
great video. complexity theory was only a small subsection in my algorithm theory class, but probably the most interesting part. this video gave a very nice refresher on it!
Magnificent! This was very enjoyable!