I have a 16x16 grid to fill up with 4 different sized blocks listed below:
16x16 16x8 8x16 8x8
How many different combinations of 16x16 grids can I make while filing the grid up completely?
Just to clarify the rules a little bit, I can use multiple instances of the same block like this image below shows:
I can also use mixed typed of blocks in any order like this:
I have searched online for algorithms related to my question, but the best I could find were permutations that show many ways you could re-arrange a set of numbers.
I worked out by hand a small sample set of a 2x2 grid and 2 block sizes (1x2 and 1x1), but the result wasn't the same as the number of permutations, because I could make 3 different types of grids while the number of permutations was only 2. (See the 3 examples below):
I also found this question here, but the question adheres to a different set of rules than what I am trying to follow as I have no concerns about containing duplicates of blocks in any part of the grid, just that the grid is completely filled up.
I would define the counting sequence from largest pieces downwards:
what's the largest piece? 16x16
does it fill the space? Yes. 1 counted
are there similar configurations? No
We then repeat this algorithm until we've run through all pieces. This cycle gives 3 for 16x8 (16x8+16x8, 16x8+8x8+8x8, 8x8+8x8+16x8.) another 3 for the 8x16 piece, and 1 for the 8x8.
So we have 8 configurations (without counting flipped or rotated variations.)
For larger sets, notice how once we block off some of the area with our current largest piece, we perform the algorithm internally. This guarantees the coverage of all states. This method of working downwards generalizes to any set of objects in any space.