Solving the "Five Squared" puzzle

2020-03-25 math programming

I’ve had this puzzle called “Five Squared” (חמש בריבוע) for a long time but never solved it. It’s a 5x5 grid broken into a handful of rectangles (two 2x1 and seven 3x1) with symbols on them, and the objective is to construct a square, out of those rectangles, where each row and column has all the symbols (no repeats).

I don’t really have a knack for these puzzles, but recently my son got interested in it and kept asking me to help him, and that motivated me to work on it. I played around with it a little and, of course, got nowhere. Then I decided to try to brute force it on a computer.

It turned out to be pretty hard to brute force! And before I could write an algorithm to effectively brute force the game, I had to study it to gain some understanding of the structure of the puzzle. I think of it on two levels. First, there are only so many possible ways of tiling the square with the 2-pieces and 3-pieces (ignoring the symbols printed on them), and it’s important to enumerate all of them. Second, for each layout/tiling of the pieces, we have to consider all the permutations of the pieces, including the possiblity of flipping each one end for end.

If you’re interested in solving the puzzle without reading the solution, here are some hints in order of usefulness:

There are 4 solutions, but they are all very closely related.
Look for obscure layouts. The two layouts that have solutions are off the beaten path, not what you’d come up with unless you approach the puzzle systematically. The two layouts with solutions are also closely related variants of eachother.
Try the first two layouts in this diagram.

Finding the layouts

The way I approached finding all the layouts was to place the two 2-pieces and then try to fill in the rest of the space with 3-pieces. Most of the time, you can’t! And, paying attention to symmetry, there are fewer cases to investigate than it seems at first glance.

Here’s an example of fixing the 2-pieces and then trying to fill in around them. In many cases, the rest of the layout is forced by constrained spaces (<3 wide). In the cases where the layout isn’t fixed, it’s necessary to explore all the possibilities.

Now, there are a lot of ways of placing those two 2-pieces, but many are redundant because of symmetry: rotational symmetry of the grid, and mirror symmetry across diagonals or middle row/column. It took me less than an hour to try everything, and in the end I found 24 distinct layouts:

The top six are just what they look like. The bottom six all have this 3x5 sub-grid which admits three different tilings (illustrated at the bottom), which account for 18 of the layouts. I believe these 24 are all possible layouts, modulo symmetries of the puzzle.

When I was playing with the puzzle, I pretty much only encountered the bottom row of six. It turns out that the key to the puzzle is finding the more exotic layouts. It’s very easy to generate a puzzle like this by making a Latin square and chopping it up into whatever layout you want. In retrospect, it seems that the key to making this puzzle was picking a layout that was sufficiently off the beaten path. Aside: I was wondering if every copy of this puzzle has the same exact arrangement of symbols on the pieces as I have, and I’ve decided that’s probably the case because those exact pieces are printed on the puzzle’s box.

Permutations

With the layouts in hand, I wrote a Python script that simply goes through every layout, and goes through every permutation of the pieces, and tries it. Actually, I wrote the script before I did the exhaustive search, with about 20 of the layouts, and was frustrated that it didn’t come up with a solution!

I wanted to use Python’s itertools.permutations to generate these permutations, but ended up doing something custom to deal with the option of flipping each piece. I hardcoded the symbols for the seven 3-pieces and the two 2-pieces, and then I just needed to permute those 7 and those 2… but I also had to allow for each to be flipped. So in total, there are (14 * 12 * 10 * 8 * 6 * 4 * 2) * (4 * 2) = 5,160,960 permutations. The first 3-piece can be any of the seven, in either order, so it has 14 choices. The second 3-piece can be any of the remaining six, in either order, so 12 choices, and so on. Then a similar thing for the 2-pieces.

Solution

Well, the script is ugly and slow, but it worked. It comes up with 4 solutions, but they’re all very similar.

Attribution

I used Piskel to make the diagrams.