Problem 61089. Find Solutions to Edge-Matching Puzzles

I was intrigued by some edge-matching puzzles I came across when visiting my parents over Thanksgiving. "An edge-matching puzzle is a type of tiling puzzle involving tiling an area with (typically regular) polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match" (Wikipedia). For more information, see the full article: https://en.wikipedia.org/wiki/Edge-matching_puzzle. In our case, we will be dealing with a 3x3 square grid, although your solutions will be easily adaptable to larger grids and different polygons. Let's take a look at a typical example:
In this example there are eight options for each tile edge: one of four colors paired with either the top or bottom half of a bottle. The goal is to arrange all 9 tiles so that the edges match colors and make a complete bottle. You can see that this puzzle is unsolved as the top left and bottom left tile edges do not match. These puzzles are surprisingly difficult to solve by hand as I quickly realized. There are a total of 9! * 4^9, or over 95 billion, possible ways to arrange these 9 tiles in a 3x3 grid. I gave up and decided to let the computer do the thinking.
Your task is to write a function that will take a deck of 9 cards and find a valid solution. The deck will be given to you as a matrix where each row represents a tile, and each column represents the edges in clockwise order. For the example, I decided to assign each edge a number based on the color: red = 1, blue = 2, green = 3, cream = 4. The number is positive if it is the top half of the bottle and negative if it is the bottom half. (The numbers can represent anything, in my case they were 4 different cats). From left to right and top to bottom, the input would look like this:
deck = [2, 1,-3, -4
-2, 1, 4, -3
-3, 2, 4, -1
-1, 2, 3, -4
-4, 1, 3, -2
-4, 1, 3, -1
2, 4,-1, -3
-3, 2, 4, -2
-3, 1, 4, -2];
Your solution should output a matrix specifying a valid tile order going from left to right and top to bottom (first column) and how many times to rotate the tile clockwise (second column).
solution = [2, 0
3, 0
8, 0
1, 1
5, 0
6, 0
4, 0
9, 0
7, 1];
Solve

Solution Stats

100.0% Correct | 0.0% Incorrect
Last Solution submitted on Dec 03, 2025

Solution Comments

Show comments

Problem Recent Solvers2

Suggested Problems

More from this Author3

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!