IQ blocks is a puzzle, where you have to fit these little plastic pieces into a square frame.
Two years ago my (then) four year old son discovered that there is more than one way to arrange the pieces in the frame, which led me to ask “How many ways are there”?
I decided to write a program to figure out how many ways there were to arrange the pieces in the frame.
My first attempt was to use brute force. I figured there are 64 little squares on the board, and any one of them could be occupied by one of ten pieces, so I’ll just generate every possible string that’s sixty four digits long made up of every digit from 0 to 9, reshape that string into a square, and then check each one of those squares to see if all of the piece shapes are accounted for.
This approach suffers one major flaw. The mathematically inclined will note that there are 10,000 trillion trillion trillion trillion trillion possible arrangements. “No problem”, you say, “the computers these days are so fast”. Calm down buddy. The fastest supercomputer in the world can perform at 33.86 petaflops, which is a mere 33.86 thousand trillion computations per second. If we covered the entire surface area of the earth with these supercomputers, and we assumed that checking one board orientation is considered one computation, it would still take several trillions of trillions of years to solve this.
Look at that last picture. Notice how most of the “pieces” are not even contiguous. The above approach is considering many scenarios that are not relevant to our game. Also this approach considers possibilities where all squares are the same color, or only two or three colors etc.. These scenarios are also not relevant for our problem. The advantage of this approach was that it was easy to write the code.
I realized I would have to write a program that would simulate playing the game. This would require much more work. I would have to teach the program how to respect the boundaries of the board, check for overlaps, check for gaps between pieces that couldn’t possibly be filled etc.. Work, but doable. Then I hit the real problem.
I had to find a way to have the program cycle through every possible way of putting down the pieces. There are ten pieces, each one of which could be potentially be oriented in eight ways. (Some pieces are symmetrical, so ultimately there are 62 possible piece orientations).
Each piece could be placed against the previous piece in several different ways.
To complicate matters, I couldn’t just cycle through all of those 62 orientations, because once one orientation has been added every other orientation of that piece should be removed from consideration.
I tried in vain for quite some time (in my spare time between semesters over an almost two year period) to set up a very complex queuing system to map out in advance all possible ways to lay down the pieces. A few weeks ago several key insights allowed me to move forward.
- I don’t have to consider every possible way to bring one piece up the one before it. I though of a new idea, the idea of the ‘next open spot’. Look at the board, look for the uppermost leftmost space that’s not occupied.
This spot will need to be occupied at some point. All I have to do is consider the possible ways to fill that spot.
Any other way for that next piece to fit against the current piece will be accounted for in another step. For example;
2. I don’t have to plan out everything from the beginning, I can plan out one step at a time. I can go through each possible way to put down the first piece, and take a ‘snapshot’ of the board, keeping track of which piece has been placed, which pieces remain etc.. Then I can cycle through all of these snapshots looking to see how I can put down the next piece, and continue in this way until all the pieces have been placed.
I had been working exclusively in C++ until I recently started to explore Python and R, and thought I would start this project anew in Python. This would prove to be a very significant move for outcome of this project.
I was up and running, I had the program find all possible ways to put down the first piece. Forty six ways in all.
I got very lucky. Notice how in all of the above scenarios the piece doesn’t leave an open space in the upper left corner. I did write a function to check for gaps, but it wasn’t working properly at this stage. But somehow the problem was averted anyway. How?
I represented each piece as a matrix of zeros and ones. Matrices are rectangular. I was trying to fill the uppermost leftmost spot. Maybe the uppermost leftmost spot in the matrix was a zero, in which case putting that piece in place wouldn’t fill the spot I was trying to fill. I had the program look at the matrix and identify the uppermost leftmost filled spot, and set that part as the part that will go in my next open spot. Sometimes this had an ambiguity. Uppermost or leftmost?
I had the program try both. An unexpected benefit of this process was that many gaps were thereby averted automatically. For example, look at the piece on the right in the above picture. Consider the leftmost part. If I would try to put that in the upper left corner of the empty board the top part of the piece would be out of bounds. Similarly if I would try to put the leftmost part of the top part in the upper left corner of the board the leftmost part would be out of bounds. Great!
Another thing I noticed is that I don’t really need to check for gaps. If there would be a gap it would end up being a ‘next open spot’ fairly soon. If no piece would be able to fit in that gap, this sequence of pieces would anyway become a dead end. So I proceeded without a working function to check for gaps. This ended up being very beneficial. When I finally got my gap checking function operational I noticed that it significantly slowed down the speed of my program. If it was an essential function I probably could have found a way to tweak the algorithm for increase efficiency, but I was able to make do without it.
So, as I was saying, I’m up and running. The program generated every way to place the first two pieces, 1,604 ways.
Notice that some of these are obvious dead-ends, for example, the second from the left in the fifth row. This will take care of itself, because no piece will be able to fit in that space when I try to add a third piece.
OK, three pieces done. 29,095 ways. Again, note how some of these are dead-ends.
Four pieces done. 224,255 ways.
At this point I’m starting to feel pretty confident that this is working the way it’s supposed to. It doesn’t look like any possibilities are being overlooked. No boards are being produced that have overlaps or pieces that are out of bounds. Some are dead-ends, but these get worked out on their own.
A mathematical note: In theory, how many ways are there to lay down the first four pieces? There are 62 possible piece orientations, some pieces have eight unique orientations, some only two. Best case scenario assumes that the pieces with most orientations are placed first, so the first four could be put on the board in 62 x (62-8) x (62-16) x (62-24) ways, or 5,852,304 ways. Worst case scenario, 62 x (62-2) x (62-6) x (62-10) or 10,832,640 ways. It would appear that we are doing very well for ourselves, the program rejected over 96% of those possibilities as infeasible.
Moving right along to place the first five pieces. Small problem. My computer runs out of memory midway through the computation. Even if I clear out all of the one, two and three piece scenarios from memory, my computer can’t handle holding all of the four piece and all of the five piece scenarios in memory at once. Now what?
Now is where I find out how lucky I am that I chose to use Python. (Also notice all of those nice 7×7 and 8×8 plots above. Python made that a breeze. It would have taken much more effort to do that using C++). Python has a library that allows serialization. Serialization is where the program can take any of my user-defined objects, and dump them into a file, and allow me to reload them later. So now what I can do is take the first 10,00 four piece scenarios, use those as a basis to compute the next round of five piece scenarios. Dump those. Then get started on the next 10,000 four piece scenarios etc.. until all of the four piece scenarios are done, and move on in a similar fashion with the five piece scenarios. I also now realize the importance of choosing to compute one round at a time, because if I would have mapped out the whole problem at once, like I initially tried, I never would have made it due to lack of memory.
Five pieces placed. 1,195,714 ways. 938MB of data, a little less than 2 hours to compute.
Six pieces placed. 4.1GB of data, about 7 hours to compute.
Seven pieces; 13.5GB, 17 hours to compute.
Eight pieces; 23.4GB, 54 hours to compute.
Nine pieces; 12.7GB, I forgot to record how long it took.
Ten Pieces; 126MB, 11 hours.
I now had a number. 101,972. How can I verify that this number is accurate? I knew from the beginning that there should be eight different ways to represent the same winning board. Each scenario could be rotated, and each of those could be flipped. So the sniff test here would be too see if that number is divisible by eight. 101,972/8 = 12,724. Wow! It passes the sniff test. I had the computer find the unique winning boards (check for flips and rotations) and in fact returned 12,724 unique boards. So I’m pretty confident that this is the correct answer. My main confidence, of course, comes from my observation at the various stages of the game, and seeing how we don’t seem to be dropping any viable moves at any given step.
Another mathematical note; In theory ow many ways are there to lay down the ten pieces? Best case scenario (again placing the less symmetric pieces first) yields 77,868,416,102,400 ways. We only have to consider the order the pieces are placed, and not how many ways there are to place the next piece, as explained above. 101,972 produce winning scenarios. That’s less than a billionth of one percent.