But how hard IS Flow?
Вставка
- Опубліковано 14 січ 2024
- Have you ever played the game Flow or NumberLink? This video does a deep dive into the world of the Flow puzzle by taking a brief look at its history, then exploring its place in the world of complexity theory.
This video is dedicated to ML for playing the game alongside me and listening to me explaining the research that went into this video. It is also dedicated to GS and JH for always entertaining me in discussing the random puzzles/problems I come up with. Lastly, this video is dedicated to RG for inspiring passion in me and encouraging me to continue my journey of teaching.
I also would like to address a couple of questions that you may come up with while watching the video:
Q: You said that we should consider an arbitrary 3SAT formula, but then proceeded to use a specific 3SAT formula.
A: Good point. Choosing a specific 3SAT formula was solely done for the purpose of visualization. However, the procedure of constructing the graph is generalizable because it works for any 3SAT formula (create vertices for each variable, each clause, etc.)
Q: I'm confused as to what the difference is between P and NP. The "friends subset" question doesn't seem that hard since we used brute force. Didn't we essentially use brute force for the "oldest person" question?
A: Yes! Both are essentially brute force. The difference appears in the amount of "queries" you have to do. For the "oldest person" question, you need to query every person exactly once. So if there are n people, then you need to only make n queries. For the "friends subset" question, I would have to query every group of 8 people. There are (n choose 8) = (16 choose 8) = 12870 such groupings. The second problem requires many more queries and grows at a faster rate.
Finally, I would like to thank Grant (3Blue1Brown) and the team that develops manim for the brilliant tool that is manim.
Music Credits:
'Filaments' by Scott Buckley is under a Creative Commons license Attribution 3.0 Unported (CC BY 3.0)
@ScottBuckley
Music promoted by BreakingCopyright: bit.ly/filaments-song
You know you’ve played a lot when you recognise a lot of the puzzles
or when you click the video simply cause you see the thumbnail and go "wait, someone is talking about this game?" lol
who asked?
@@rurathn5534 No one asks for any comment on UA-cam (except maybe the UA-camr), just like no one asked for yours. What a useless comment.
For some reason I bearly take longer then 10 seconds to solve those
I've been playing 1918 perfect daily streak now
I like how "3blue1brown style math explainers" are just straight-up a _genre_ on youtube now.
It's because they all use the same program to do the animations, it's called Manim
@@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.
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
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
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.
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".
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?
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 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.
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 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
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
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@@robertbingham8053
@@robertbingham8053 hexes to me is harder but just at the biggest level
The sound effects are without a doubt the best part of flow
Is this a joke?
Well, wasn’t expecting a Flow Free essay video to be on my 2024 bingo board. Well-thought out video, by the way.
I remember playing this game when I was very young. Brings back memories.
same
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 was basically the last section of my intro to algorithms cs class in university. Good refresher.
Flow free has had a permanent Tetris effect on my brain I’m excited to watch this
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
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.
This video reminded me that I needed to do my daily flow puzzle. Thank you. 17 day streak so far.
This video gives me flashbacks to comp sci. Incredible work
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!
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.
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 😊
I used to play this on an iPad. Very enjoyable and relaxing. Even on the highest levels, although they could be challenging, I could usually solve them in a few minutes.
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
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.
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)
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
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!
@@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!
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!
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 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.
This was so much more than a video about Flow! Fantastic work!!
Flow really brings back memories. Guess I need to redownload it now
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.
i was waiting for such a video since such a long time! thanks a lot
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 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!
i literally opened youtube to find something to put on while playing flow, and then i saw this recommended hahaha. looking forward to it!
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!
Omg this speaks to me. Had this app forever but now again getting into it
7 minutes in and I wish I had this video while I was in university. Good job explaining P, NP and NP-complete.
This game was a fun time passer back in the day. This was a good walk down memory lane
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.
Intriguing and well made, I can’t wait to see more!
Crazy how you dropped the most well made video on UA-cam about flow free
i havent thought about this game in 10 years, thank you for reminding me of its existence
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)
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!
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
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 am currently playing this game as this video was recommended to me, perfect way to get my attention
Magnificent! This was very enjoyable!
I played it so much that I was constantly waiting on new packs. Great memories
What a great video, thank you
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
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)
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 have taken complexity theory in university and i love this video! well done, super interesting, love the theory behind 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).
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!
I got lost when you did the transformation, but I still watched through! I'll come back tomorrow and see if I can understand better
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~
Omg I haven’t played Flow in years! What a fun game. Neat video!
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 have done so many levels in this game it’s absorbed so many years of my life
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 have perfected every level in the base game and hit a daily streak of about 600 days now. I love it
It is so damn cool to see manim being used so widely for videos like this. Grant from 3b1b is such a gamechanger.
Great video, keep it up!
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.
Wow, surprised I haven't seen this account before. Great video!
That was a slick proof!
Sometimes, figuring out one line makes everything else literally fall neatly in your lap.
I’ve played this game a lot, and it feels very easy to me. I use it to kill time or stim if I’m doing something else. I don’t really understand any of the math jargon in this video, but it was interesting to see just exactly HOW puzzles work, mathematically. I think the way I play puzzle games like this are similar to the way that Marta (from Knives Out) explained why she can beat Harlan at Go: “I’m not playing to beat you, I’m playing to create a beautiful pattern.” thanks for the video!
I love this game, i use it as more of a zen time killer
For whatever reason I'm really good at spacial puzzles, and i can solve almost every Flow puzzle of any grid size in a couple of seconds. Just as fast as my fingers can move
this video just unlocked a core memory
🎀 I don't understand a word of this video, but I'm glad it exists
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 used to play flow free while on the bus to college, as the app is only really tollerable when there's no internet, because of the ads.
but during my college days, I'd finished almost all the puzzles. as the puzzles get harder, you quickly learn strategies to solve them. at the peak I'd get through about 120 or so puzzles in the 30 minutes bus ride.
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 kinda almost forgot of this game. loved playing the crazy 13x13 puzzles
Years ago I played this game so often, there was one weird level I was struggling to get through, had a dream that night doing it, woke up, grabbed my phone, and did it
i think i liked this game a lot because both ends of the difficulty scale have their own challenges
while bigger ones are usually harder than smaller ones, its a lot of fun to speed through the smaller ones as fast as i can go
it probably does this game a good service that the smaller puzzles aren't too difficult especially because of mathematical limitations with variation
with all the packs they've added there's a very good chance i've solved the same ones twice maybe at different rotations or flipped, there's gotta be hundreds of 5x5 and 6x6 puzzles
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"
Here's a reduction of 3-sat to version 2:
For each variable, have a pair of nodes to be connected. For each option it can have, create a path between them. On each of them, for every time it appears in a clause, make 2 consecutive patches of at least 3 nodes each. (It's best to make exactly 3. However, any number is ok, unless it makes the reduction non-polynomial.) The first one of the first one and the last one of the second one are the outer ones, and vice versa are the inner ones. For each clause, link each term to the next one in a cycle (i.e., last to first) by adding two edges. The edges should connect the inner ends of one to the outer ends of the other one
I love this game! I have a star for almost every pack in Flow Free; meaning I've solved all 150 boards in those packs with the minimum amount of moves possible. Still working on a few of the super hard ones.
A small note that solving P-type problems "quickly" is a very arbitrary measure. Some P-type problem solutions can take insanely long amount of time to solve. The difference lies more in the difference between solving the problem and checking the solution than taken time - a classic example is prime factorization. If you have million digit number, calculating it can take quite some time. Or you can have a solution which you can check way faster by multiplying the factors.
well polynomials are allowed to have huge degrees or even just huge constants. A problem that always takes (1 heat death of the universe measured in seconds) steps to solve is a constant time problem, but for common sense purposes not "quick" to solve. However in the timeless world of computational complexity it gets surpassed by everything.
I like to describe NP hard problems as "have basically 0 clever solution besides brute forcing" and P problems as ones that...aren't that. Don't know if that's any better.
Wow i literally forgot about this gor years, thanks for reminding me lol
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.
You he me right up until around 13:41 which is where my mind said this is too much.
I enjoyed the video none the less
Excellent video 👌👌
I’ve played and perfected so many flow levels that I can get the solution for any by just looking at it for a few seconds
I thought this was going to be about fluid flow, and I almost clicked away when I realized it wasn't.... until SURPRISE ALGORITHMS AND COMPLEXITY THEORY!
Great video!