Crackerblocks: computing solutions for IQ Block game

The IQ Block game is a puzzle where the player must fit eight shapes into a square space. The challenge is to find as many ways as possible to do it.

The box says there are more than 40 solutions! So how many are there?

I wrote a solver to crack the IQ Block game. The code is available here and a detailed description is at the end of the post. The solver found 264 solutions from 33 placements. Many of these solutions were duplicates, which meant there were 64 unique solutions.

Here they are:

I was surprised that there were so many unique solutions. “More than 40 solutions!” suggested to me that there were less than 50 solutions. In the end I found 64. Perhaps the manufacturer has not run a solver to check the total number? I’m pretty sure for marketing purposes, the potential number of solutions must appear as big as possible in order to infuriate puzzlers!

How the puzzle works

There are eight blocks, each with a unique shape. They must fit into a square space which is 8 x 8 units with no gaps. Each block is 8 square units in size and the space is 64 square units.

The instructions are to fit a block in the top left corner and then fit the remaining blocks to find a solution. This tells us that the orientation of the space is important. Rotations and reflections of a solution will count as different solutions.

How the solver works

The puzzle can be treated as an 8 x 8 image where we fill the image with pixels of eight different values. I coded a solution in IGOR Pro to solve the puzzle this way, by brute force. This approach, although slow, meant that I am certain that all combinations have been attempted. In the end, the code ran 13 times longer than it needed to, since all solutions were found after only 5.8 x 10^8 iterations.

The code makes 8 matrices one for each block. The pixels corresponding to the block are filled in and then these matrices are duplicated (and reflected and/or rotated) to find all possible unique orientations for placement. So blocks have between 2 and 8 possible orientations. Since all eight blocks must be placed for a solution, we can generate all the permutations of these orientations (131072 permutations) and then select from those in all possible combinations (40320). This is 5.28 x 10^9 ways that the blocks can be placed.

The first run was way too slow…

Some optimisation was required to save on computing time. One improvement I made was to check if the placement would mean that the first (or last) block, in the top left (or bottom right) of the image, would result in a trapped empty pixel. That situation would mean a solution was impossible, so the attempt can be skipped to save time. In the final run 2.5 x 10^9 attempts were made and 3 x 10^9 attempts were skipped with that change, which halved the compute time. There were many more inefficiencies in my code and it could definitely be improved to go faster!

The program had one rule for fitting the blocks in a predetermined order. This was to place the blocks sequentially in the next available space. This strategy gives pretty good coverage of the total search space, but it is incomplete. We know that it is incomplete since not all solutions were found using it, however, the strategy found enough solutions that we had four-fold saturation in the end. What does that mean?

Well, the program found 33 solutions using its search strategy. Each solution could be rotated and reflected to give 8 variations of each solution. So the program found 264 solutions. Now, many of these will not be unique, so using a distance matrix to reject identical solutions, these were whittled down to 64 solutions. These 64 solutions corresponded to the first 8 placements that were found. So, because 64 is greater than 33, we know that the search strategy was incomplete. However the duplication of solutions means 75% of the later solutions were identical to the first 25%. This makes it unlikely that there are any further solutions.

Knowing the maximum number of solutions, would allow us to optimise the code to find all solutions in the fastest way. However, we only knew there were more than 40 solutions at the start, so the code had to be open-ended to find all the solutions.

Conclusion

The IQ Block game is a fun puzzle with 64 solutions. They are available on this page if anyone is stuck!

The post title comes from “Crackerblocks” by Ozric Tentacles from their Erpland LP. Plenty of songs in my library with “block” in the title, but this was the most appropriate.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.