Jigsaw Puzzle-Solving Robot Has the Fun for You
Shane Wighton is building an engineering marvel of a robot that will solve a massive 5,000-piece jigsaw puzzle.
Jigsaw puzzles are a lot of fun and completing them takes a surprising amount of problem-solving skills that humans are uniquely suited for. With a typical jigsaw puzzle, the printed image acts as a key reference for determining piece location. But there are special jigsaw puzzles that are all a solid color, forcing solvers to find piece location based solely on the unique shape of the edges. Such puzzles take months of trial and error to solve — and that is for a human. Building a robot to solve those solid-color jigsaw puzzles is quite the challenge, but Shane Wighton’s engineering skills were up to the task.
As Wighton says, this is the future and robots should be able to have fun for us. But this is still quite the engineering challenge. To explain how Wighton made this work, we’ll start with the simplest part of the equation: the motion system. The robot resembles a large CNC router and that is pretty close to what it is in practice. The sturdy wood table supports a CoreXY kinematic motion system, which allows for very fast movement. It can pick up individual jig saw pieces using a vacuum suction end effector like you’d find on a pick-and-place machine. A vacuum suction table, like the kind used to hold plywood down on CNC routers, keeps the pieces i place after the robot drops them.
That’s all very impressive and it was easy compared to the rest of the robot. For this robot to solve the puzzle, it must compare every edge of every piece to every edge of every other piece. For a 5,000 piece puzzle like this, with 4 sides on each piece, the result is about 1.82x1077337 comparisons. If the robot made one comparison per second, it would take 4.2x1077319 times the age of the universe to complete the comparisons. Wighton’s algorithm performs comparisons much faster than once per second and presumably takes shortcuts like omitting solved edges and pieces, but he still estimates that it would take around 3,000 years to solve the puzzle. In his next video, he plans to improve the algorithm and will go into more detail at that time.
Until then, it is worth understanding how the robot compares pieces. Wighton designed a magazine for the robot to grab pieces. It then places the pieces on a backlit window to take a photo. A regular camera would distort the image and make the edge measurements inaccurate, so Wighton used a specialized (and very expensive) telecentric lens. That lens produces an image that looks as if it were taken from infinitely far away, removing all distortion so every edge is perfectly perpendicular to the plane of the image. With that distortion-free image, Wighton could use computer vision software to detect the piece edges and gather accurate measurements for his solving algorithm.
To demonstrate that, Wighton made a custom 45 piece jigsaw puzzle. The robot solved that puzzle successfully, but even this small puzzle took around an hour and a half to complete. The time per additional piece increases exponentially, not linearly. To see how Wighton manages to overcome that overwhelming hurdle, be sure to catch his next video.