# Match the colors on the edges of the rectangles - is it possible?

In April 1971 (it says so on the back of the cards) I made the following puzzle which requires one to form a square with adjacent colours being the same.

1. Can this puzzle be solved and, if yes, what is the solution?
2. Without actually solving the puzzle, is there a way of checking if there is a solution to such a puzzle?
• @bobble I question why the statement is necessary unless it's part of solving the puzzle. If the author solidifies this statement it in a comment and the community concurs, then I will retract my close vote.
– Taco
Commented Sep 28, 2021 at 17:49
• I know that I manufactured the puzzle from card etc but I honestly cannot remember as to the origin of the puzzle as it was over 50 years ago. In that era I would have read Martin Gardener in Scientific American but have been unable to track the puzzle down in that publication. The puzzle has been in and out of my drawer over the years. I think that it is not unreasonable to ask if one can decide whether or not it is soluble without finding the solution. Commented Sep 28, 2021 at 17:57
• If it was from Martin Gardner in April, it might be an April Fools' hoax like his 1975 map coloring one. Commented Sep 28, 2021 at 18:27

There is a solution which is unique (up to rotation).

If you want to solve it yourself, here is a hint describing the orientation of the pieces:

In the top left and bottom right are vertical pairs of pieces, and in the top right and bottom left are horizontal pairs.

Solution:

To be honest, I used a computer to solve it. In general there is no quick way to find a solution to an edge-matching puzzle, or prove whether there is or isn't a solution except in some specific extreme circumstances. Edge-matching type puzzles as a category falls in the NP-complete class of problems.

• Thank you very much for the solution. I can now continue to allow my grandchildren to try and find a solution with a clear conscience knowing that the puzzle can be solved. Commented Sep 28, 2021 at 21:47
• Ignoring the rotation of the whole square, how many possible ways are there of arranging the eight cards to form a square? Commented Sep 29, 2021 at 11:35
• What computer algorithm was used to find the solution? Commented Sep 29, 2021 at 11:37
• @Farcher Ignoring colours, there are 36 ways to fill a 4x4 square with dominoes. Using our coloured dominoes, each of these arrangements can be filled in $8!\cdot 2^8$ ways. Up to rotation, we then have $8!\cdot 2^8\cdot36/4=92897280$ ways to construct the square from the pieces. I used my own Polyform Puzzle Solver to solve it, encoding the pieces as 6x12 rectangles, and adding bumps and dents to the edges to represent the colours. Commented Sep 29, 2021 at 12:54
• Brilliant. Thank you very much for such a quick response. Commented Sep 29, 2021 at 13:00

Solving strategy:

There are 2 symmetric pieces 3 and 5 (1st on second row), so it is a good idea to look at them first

Looking at 4-subsquare solutions (as a start , or because we think it is the only way):

5 can only form a square with 3, so they are matched
checking the others:
yellow: 7 can be mathed with 2 (and not 4 because of the other color)
blue: 6 and 8 can be matched with 1 and 4
green: 6 and 8 can be matched with 1 and 4
(red can be skipped: covered by the other color since there are no double reds)

So 35 and 27 must be paired

If we pair 1 with 6, we get opposing red-red and green-green sides not seen elsewhere, so they cannot be paired
So our pairs are 35, 27, 18 and 46

27 and 18 both have 2 red-green sides that match with each other but not with the rest. Those sides must be all outside, or two must be adjacent and two outside.
This gives us the three bottom options as possibilities.

The right one needs 2 clockwise green-yellow sides; only one is available
The other 2 force the one clockwise green-yellow side, and the last piece (only) fits in the top right configuration.
So a solution is found. Note however that there might be solutions with only 1 or 2 smaller squares.

• Thank you for this solution which I have enjoyed investigating. However I do not feel that I can give you the green tick even though it is more elegant than the computer generated answer of @JaapScherphuis as your solution was published later. Commented Sep 29, 2021 at 21:46
• @Farcher it's not a race. To elaborate: there is no written or implied rule, that the first answer has to be accepted Commented Sep 30, 2021 at 4:49
• I did not imply that it was a race but once a solution has been published it is often easier to find another method. My last statement is in no way a comment regarding the excellent solution produced by @Retudin. Commented Sep 30, 2021 at 6:40
• @AndrewSavinykh As you are much more experienced on this site can I ask you which of the two answers you would give a green tick to and why? Commented Sep 30, 2021 at 6:41
• @Farcher In my opinion Jaap answered your question better than me. 1 It is solvable 2 To check if a puzzle is solvable without actually solving it, writing a computer program is often/in this case a good approach. I added onto that by showing that actually solving is does not require trying many branches. It is up to you to decide who you think gave the better answer though. (And one can debate if a computer solution is 'without actually solving') Commented Sep 30, 2021 at 7:27