Worlds hardest jigsaw vs. puzzle machine (all white)

How long do you think it would take you To solve a 5 000 piece all-white puzzle I think it would take the average person A really long time like years but I Think that a computer and a robot can do It really fast like less than a day if I Can get my robot working in my last Video I made a robot that can assemble Puzzles but it’s real dumb it couldn’t Do more than maybe 50 pieces so ever Since I’ve been working on an algorithm Which will hopefully allow the robot to Take big puzzles with like 5 000 pieces Figure them out and then assemble them Quickly all white puzzles are really Hard because there’s no picture that you Can look at to figure out if pieces will Fit together if I want to figure out What piece connects to this piece I have To pretty much pick up every single Piece and test it to see if it fits if You do the math this works out to Somewhere around 30 million comparisons That you would need to do and that’s why I say it should take a human years I Wanted to do this project because I love Seeing robots do something that’s hard For humans and I also really wanted to Talk about computer science so I get to Do both here’s my plan for solving the Puzzle I’m going to give the robot each Piece one at a time so that it can get a Picture of every piece And then it will extract the shape of

Every piece from the photos and then Think really really hard about all the Ways that it could assemble it until it Finds the right one and then it’ll use That plan to actually assemble the Puzzle when you list it out like that it Doesn’t sound that bad but I’ve spent The last several months trying to solve This problem it is without a doubt the Hardest project that I’ve done but it is An awesome opportunity to talk about Algorithms and software it’s the reason That I did it so let’s get into it I Made a few Hardware upgrades since the Last video It’s better faster stronger Less breakable but I’m not going to get Into the details of those because I want To focus on the software though the key Takeaways are number one the magazine is Gone because it is a reliability Nightmare and I made some upgrades to The business end that limit the range of Motion of the robot and it can’t Physically assemble my 5000 piece puzzle Anymore so I was thinking about it a bit More in five thousand piece puzzles are Totally overrated what will be really Hard is a four thousand piece puzzle no One makes a four thousand piece All-white puzzle so I got a normal Puzzle and I painted it white with all That done all that’s between us and a Soft puzzle is our imagination and a lot Of software except I forgot my lease is

Up on my shop so I have to move all of My stuff this took me so much longer Than I was expecting like six weeks to Move everything clean up all the damage At the last shop and get set up at the New place moving a very delicate puzzle Solving robot is nerve-wracking but I Only slightly broke it Welcome to my new workshop there is a Lot of stuff it is packed tighter than a Neutron star what it doesn’t have is a Lot of room to do stuff but that’s okay Because I have shipping containers that Are packed very very packed all right Let’s get back to the robot the first Step to solving the puzzle is getting a Picture of every piece I’m going to give The robot each piece one at a time it’ll Take a picture of each piece with this Very accurate camera with a telecentric Lens this takes about eight hours thank Goodness I only have to do it once all Right so I’ve got 4 000 pictures of all The pieces but that doesn’t really do me Any good I need to extract the shape of Each piece from the photos here’s how I Do that each picture is made up of a Bunch of pixels that have a color and The pixel showing the background are a Very different color than the piece we Can say any pixel that’s similar to the Color of the background isn’t the puzzle Piece and every other pixel is the Puzzle piece so we’ve got a blob that’s

The shape of the puzzle piece but what We really care about is the shape of the Edge because that’s what does all the Connecting so the next step is to Extract it so all we need to do is look At every pixel that’s in the piece if That pixel is next to a background pixel We say that pixel is part of the edge And if you do this for every pixel in The image you get the entire edge of the Piece so at this point we can throw away The image and treat the pixels as points In space that form the edge of a Complicated polygon we want to do this So that we’re not constrained to pixels When you think about solving a puzzle You’re usually not thinking about the Entire shape of the piece you’re Thinking about the shape of one of the Sides so we need to take this perimeter And divide it into the four sides for The puzzle piece and once we have those Then we can start seeing which ones Might fit together conceptually this is Pretty easy you find the corners of the Piece and you divide the Contour up at Every corner but in reality it’s pretty Tricky if we zoom in on the corner it Isn’t perfectly sharp any point along This curve could be considered the Corner if I’m not rigorous about how I Define the corner some edges will appear Longer or shorter and they will not Match correctly I start by finding the

Approximate Corner locations and then I Grab a little part of the polygon on Each side of this corner and I fit a Curve to it I consider the intersection Of these two curves the corner of the Piece and it usually doesn’t fall on the Polygon so we find the point on the Polygon that’s closest to this corner Floating out in space and we split it in Half at that location if you repeat this For every corner you get four curves That are the shape of each side I’m Going to calculate this for every piece And it’s probably going to take a while But I only have to do it once I can save The result to my hard drive and then Load it way faster than it would take to Calculate it this is sometimes called Pre-processing this is going to take a Lot longer than I was expecting like Probably days times like this make me Really glad to have a super powerful Computer because instead of trying to Make it faster I can just throw a more Computer at it and it’ll hopefully be Fine so what I’m going to do is split This job into 80 smaller jobs that I’ll Run at the same time so hopefully Instead of a few days it’ll get done in A few hours I don’t think I’ve ever Talked about my computer before which is Kind of surprising because it’s my most Important tool I’ve had this thing for About a year it’s made by a company

Called Puget systems and it is a beast They asked me what specs I thought I Needed and I said I need all the ram all The CPU and all the GPU and for stuff Like poorly written programs big cat Assemblies and editing videos it is Astonishing how much time it saves me if You’re looking for a beefy reliable Machine you should check out Puget I’m a Big fan I know a lot of people are going To tell me that I wouldn’t have these Problems if I didn’t write my code in Python but if I wrote my code in Something like C plus plus I would still Be writing code so I like this trade Now that we know the shape of all the Edges we need to go through all of them And figure out which ones potentially Match the slow easy way to do this would Be to compare every Edge to every other Edge but that would be too slow this is Where we get into software optimization You may have heard people talk about This before the general idea is that you Find some kind of shortcut or alternate Way of computing something so that it Goes faster and what we’re going to try To do is find a way so that we can Directly compute which edges match a Given Edge without having to do any Comparisons so if I have an edge I can Just directly say here’s all the edges That are similar to that one without Having to compare it to every possible

Edge it’s going to get kind of weird but Also kind of awesome so hold on to your Butts we can start by grabbing one of Our edges and making an imaginary line From one side to the other and then Divide this line into some number of Equally spaced points and then at each Point we calculate how far the curve is Away from the line at that location Station this will give us a list of Numbers that approximates the shape of This curve to make what we’re about to Do easier to understand let’s pretend That we only took two evenly spaced Points if I treat the first number as an X-coordinate and the second number as a Y coordinate we can plot this point on a 2d graph if we do this for a bunch of Edges ones that are similar will be near Each other on the graph and ones that Aren’t similar will be far apart Unfortunately figuring out what points Are near a given point requires that we Compare them which is what we don’t want To do so we need to go deeper if I take A line and add it to this graph we can Calculate which side of the line any Given point falls on then if I get a new Edge and I calculate where it goes on The graph I can see which side of this Line that it falls on and I can ignore Any of the points that are on the other Side of the line I know that it’s not Going to be similar to them without

Having to compare it but this stops Being effective if I have points all Over the place but if we add more lines Dividing this graph something really Cool happens this point is on the left Side of this line the right side of this Line and the left side of this line this Sequence of left right left describes a Very small specific region of this graph And all the other regions have their own Unique sequence so for every point on This graph we can calculate the sequence That describes where it is on the graph If we keep track of what region of the Graph each point falls under if we get a New Edge we can just calculate where it Falls on this graph and directly look up What other points are similar without Doing any comparisons so I did this in 2D so that we could visualize it I used 128 dimensional space for my hash the Math is the same it’s just 128 Dimensional graph and instead of a line You have a hyperplane but the math is Really the same you just can’t visualize It and I did not invent this it’s called Locality sensitive hashing it has Nothing to do with crypto or medicinal Oils and it is an amazing technique one Other really cool thing that it’s used For is reverse image search we’re going To use the hash to find all the similar Edges for all of the pieces Hmm

I have been looking at this forever for Days and I initially thought that I did It wrong which is usually a really good Guess but in this case it’s even worse It looks like I did it right but it’s Still giving me the wrong answer it Looks like we’ve got a bad case of what Programmers call garbage in garbage out When this happens it doesn’t matter how Good your algorithm is if you give it Garbage data it’s going to give you Garbage results although in my case it’s Very subtle garbage it’s like a tiny bit Of dog poo in your brownies you would Know it from just looking at it but it’s Garbage They must have used a very dull knife When they cut out the pieces the edges Are super fuzzy which makes the pieces Look like a different shape than they Actually are This thing is a vibratory Bowl tumbler And the way it works is there’s abrasive Grit inside of it which it vibrates Really hard and if you have something That has a lot of rust on it or sharp Edges you can throw it in here let it Run for a few hours and when you come Back you have a really beautiful part so This thing is usually used with metal But I’m hoping with some very gentle Abrasive I can put cardboard puzzle Pieces in there and they won’t get Disintegrated into nothing

All right this is approximately infinity Times better All the pieces changed so we have to Scan them in again this takes about Eight hours thank goodness I only have To do it twice all right let’s calculate All the Edge matches What All right I am gonna lose my mind so the Pieces look good my code looks good the Results Don’t look good Upon closer inspection it looks like the Vibratory tumbler did a great job of Removing all of the little fuzzy things And sharp edges but it also did a good Job of changing the shape of the puzzle Pieces by grinding them down and when You take pictures of them they don’t Look like they fit together anymore Which I guess that makes sense but it is Really unfortunate this is a really Annoying problem even if I go and buy a Higher quality puzzle that doesn’t have The rough edges if I paint it white I’m Going to get paint on the sides of the Pieces then I’m going to want to put it Back in here and it’s going to mess it Up again the only thing I can think to Do is make my own puzzle I can get the Top of it painted white and then I can Cut a puzzle out of it it’ll have really Nice clean edges and there won’t be any Paint on the sides

I should have done this from the Beginning I would have saved so much Time it’s a new puzzle so I have to Rescan it which takes about eight hours Thank goodness I only have to do this Three times I didn’t realize it when I Was making it but my laser cut puzzle Has some self intersections on the Contours which turns one piece into one Really messed up piece and an extra Little chunk and it looks like there’s Only four of them I could spend a bunch Of time updating my algorithm to support Malformed pieces but that really seems Like a dumb idea I could remake the Puzzle but that would take me like a day I’m really leaning towards option C Which is just put the pieces into the Four missing spots when the puzzle is Done all right we’ve got new picks new Hash third time’s the charm Okay finally believe it or not we are Just now getting to the Crux of this Problem every side of every piece Potentially connects to multiple other Pieces and without any kind of picture On the puzzle the only way to know which Of these Edge connections is the right One is to build more of the puzzle and See if it makes sense if we go back to That original piece it has some number Of potential connections on each side if We pick one of the possibilities for Each of these sides the only way that

They work is if they share a mutual Piece in between them like this Otherwise there’s no way to connect them So even if they fit well to the original Piece they don’t make sense when you Consider the rest of the puzzle if you Do this for every piece it reduces the Number of possibilities dramatically Incidentally doing this also generates All of the possible two by two squares Of pieces that you could use and this is Where we go deeper we can pretend that a Two by two block of pieces is one big Complicated puzzle piece if both of the Pieces on this block connect to both of The pieces on another block then it’s a Valid connection we can eliminate Possible Json block unless they share a Mutual block and then you can build two By two blocks of two by two blocks which Would be a four by four block and then Keep repeating this until you can’t go Any further This part is actually really mind Bending and really annoying I spent Several weeks at this stage I could not Get it to fully complete and I did have To give it some hints to help it along I Do think with some more time I could Have it run fully autonomously but I’m fine I’m okay with that so at the End of this process most of the pieces Only have one possible connection so Then you can go through that and

Assemble the grid of all the pieces Which the robot can use to actually Solve the puzzle Four thousand pieces is a lot of pieces And it is not very fun to feed them in One by one into this robot I did want to Have an automatic vibratory ball feeder I even built one but it had a bunch of Issues and I figured it would take me Longer to fix those issues than it would Take for me to feed all the pieces in And so I’m just going to do that thank Goodness I only have to do this four Times one other big problem that I Really wanted to solve but I just don’t Have time for is that sometimes when you Put pieces down they won’t fit together Perfectly this sort of has a Cascade Effect when you click two pieces Together it’ll shift the pieces that It’s connecting to and then when you try To connect a piece to the shifted pieces It’ll get tilted and won’t seat all the Way down and I wanted to be able to scan The pieces that I put down which is why I have this other camera it’s why the Table is orange so that I can very Clearly see the pieces that I’ve put Down and it’s why I added this really Nice light to the cam camera if it can Put them in mostly the right spot and I Just have to nudge them with my finger To make them click together that is a Complete win by my book

So one thing that I like to say is that If at first you don’t succeed reduce Your expectations until you’re a success I think those are pretty good words to Live by and that’s definitely what I’m Doing here at least in theory the robot Now has everything that it needs to Solve the puzzle if I put it into solve Mode The robot expects me to load the pieces One by one when it sees a new piece it Extracts all of its details and then Looks up where it needs to go using the Solution then it rotates the part to Whatever orientation it needs to be at And then moves over and puts it down Where it needs to go All right here we go That is so satisfying All right well with this many pieces you Can’t expect them all to fit together Right I already regret not making that feeder Bowl work [Music] I didn’t see it happen but I think a Piece stuck up just barely enough to hit I was able to get it mostly back to the Right spot I think I was gonna wait until the end to push The pieces down but that crash has me Paranoid the cumulative error is really Adding up in some spots the pieces are In the right spots though so it’s an

Easy fix well except for this last row There’s a bunch of pieces that do not Belong that are being stacked on top of Each other I’m guessing this is a stupid Logic error but I’ll have to look it was A stupid bug I think it’s fixed so let’s Keep going All right it’s almost there just gotta Seat these pieces I have no idea why but only on this edge Of the puzzle some of the pieces are not Put in the right spot they’re stacked Randomly on other parts of the edge Mostly this Edge this is the last row in The simulation I’m guessing there’s Still a kind of stupid bug happening There Although I looked at the code and There’s nothing really obvious So I thought about spending a ton more Time trying to get to the bottom of this But I could also just Do this I don’t think anyone would know or even Care right there’s a few other missing Pieces this is where the messed up Self-intersecting pieces would be So we can just Put those in the right spots All right it is done I made this puzzle yet somehow I lost Two pieces I could laser cut some replacement parts But I think there’s something poetic

About two pieces being missing it sort Of matches really well with my reduced Expectations and the journey was the Destination in any case and I hope that You enjoyed it I hope you learned Something about algorithms if you find This fascinating like I do you should Consider becoming a programmer if you Aren’t already it is an awesome job Where you basically explain to a Computer in excruciating detail how to Do stuff like this I’m really curious to see if my wife is As impressed with this as I am but Before we get to that I want to talk About this video sponsor it’s a company That I think is amazing brilliant People reach out to me all the time Asking me what it is they need to learn To be able to make stuff like I do and Whenever they do it makes me really Happy because I really want to inspire People and this is why I love brilliant It’s a really powerful tool for learning Math and computer science and a bunch of Other technical stuff the way it works Is it’ll take a really complicated Subject like computer science and They’ll break it down into a bunch of Bite-sized lessons which will teach you Concepts and then reinforce it by having You work examples which is just the best Way to learn I’ve read textbooks for Years and this is exactly what I do and

Brilliant is better than a textbook Could ever be because a lot of the Examples are interactive it’s so much Easier to see and build intuition for How something works when you can Directly interact and manipulate it and The fact that they’re smaller lessons Makes it really easy to do a little bit Every day I try to spend a little bit of Time every day doing some kind of Learning and I’m always amazed when I Look back at the past year how much Progress I make just from that little Bit every day I’ve been working through Their lessons on differential equations I did learn this back in college but I Never really got it and I also forgot Everything I knew about them in all the Time since and I feel like it’s starting To click which is awesome so if you’re Interested in building technical skill You need to check out brilliant it is an Amazing tool and it’s free to get Started all you have to do is go to Brilliant.org stuff made here you can Also click on the link in the Description and the first 200 people to Do this will get 20 off their annual Premium membership and that’s it thank You brilliant for sponsoring this video And thank you for taking the time to Check it out all right let’s see what The wife thinks Hey wife

Wow I thought you said it was finished I spend months building these projects And I love doing it if you enjoyed these Videos please consider supporting them Subscribing to the channel helps me get Sponsorships and you can also support Them directly on patreon thanks [Music]

Hi, I'm ClicBot!

Would you like to see what I can do?

Leave a Comment