Last night we had dolma and Christmas movie night with some friends; my Italian/German/Irish roots would be very proud of me for branching out. Chau, a longtime friend and my dynamics tutor in college, brought a friend over. We were a household of techies...in the Bay Area...how surprising. As we sang along with Hamilton, ate olives, pita, and humus, Chau and her friend casually put together the better part of the 1000 piece puzzle in one sitting. Puzzle pictured above.

At the end, someone popped the question “What logic would you use to get a robot to finish this puzzle?”

Here are some assumptions that we made:

1. Robot does not know what the final picture looks like
2. All puzzle pieces are right-side-up
3. Puzzle is cut by a laser; the pieces are perfectly flat and edges match up perfectly
4. All pieces are distinguishable

Several ideas were offered. I mentioned edge detection but Chau’s friend brought up how computationally expensive that would be. Instead, Chau came up with a color matching process that groups pieces by their color first and then assembles pieces based on the colors at the edge of each piece. These two algorithms of the program will complete the puzzle in three steps:

1. First by filling bins with pieces of like colors
2. Assembling pieces within bins
3. Assembling bins into the puzzle

1. Color matching would work by initially filling bins with pieces of like colors. For simplicity, eight pre-existing bins will hold all the pieces of the puzzle. The bins are white, black, red, green, blue, cyan, yellow, and magenta. Pieces will be distributed between bins based on highest percentage color represented in the puzzle piece. Once each piece has been put into a bin, the color values along the edges of each piece within a bin are recorded into a matrix with four rows; one for each edge.

2. The process of assembling pieces within bins would happen each time a new piece is added to a bin. The color values of the new piece are read and  recorded into a matrix. The first five color values from each row are compared to every other puzzle piece matrix in the bin to see if there is a match. If there is a greater than 60% match (3 out of 5) of the first five color values in both matrices, the last five values of the two rows are compared. If this also reveals a greater than 60% match, a comparison of all values in both candidate rows (puzzle piece edges) is conducted. If there is a greater than 80% match, the two rows get replaced by a pair of matching integers that link the edges of the puzzle pieces. This process reoccurs until all pieces in all color bins are matched.

3. Assembling bins into a complete puzzle happens just like pieces within a bin being assembled together. Now that the bins have become a single matrix with as many rows as there are edges, the same algorithm designed for assembling individual pieces will be used to assemble bins. Assembling the bins will complete the puzzle.

My friends and I only discussed the architecture of the algorithm our robot would have to use in order to complete a puzzle. We didn't get a chance to discuss any of the sensors or actuators to put on our robot, but I'm sure the algorithm is a sufficient first step as there would be many edge cases that we haven't thought of that we'd need to handle for.

If you have any thoughts or feedback, leave a comment below 🙂

Thanks for reading!