Counting the ways to build a wall with two tile sizes

Question

You are given a set of blocks to build a panel using 3”×1” and 4.5”×1" blocks.

For structural integrity, the spaces between the blocks must not line up in adjacent rows.

There are 2 ways in which to build a 7.5”×1” panel, 2 ways to build a 7.5”×2” panel, 4 ways to build a 12”×3” panel, and 7958 ways to build a 27”×5” panel. How many different ways are there to build a 48”×10” panel?

This is what I understand so far:

with the blocks 3 x 1 and 4.5 x 1

I've used combination formula to find all possible combinations that the 2 blocks can be arranged in a panel of this size

C = choose --> C(n, k) = n!/r!(n-r)! combination of group n at r at a time

Panel: 7.5 x 1 = 2 ways -->

1 (3 x 1 block) and 1 (4.5 x 1 block) --> Only 2 blocks are used--> 2 C 1 = 2 ways

Panel: 7.5 x 2 = 2 ways

I used combination here as well

1(3 x 1 block) and 1 (4.5 x 1 block) --> 2 C 1 = 2 ways

Panel: 12 x 3 panel = 2 ways -->

2(4.5 x 1 block) and 1(3 x 1 block) --> 3 C 1 = 3 ways

0(4.5 x 1 block) and 4(3 x 1 block) --> 4 C 0 = 1 way

3 ways + 1 way = 4 ways

(This is where I get confused)

Panel 27 x 5 panel = 7958 ways

6(4.5 x 1 block) and 0(3 x 1) --> 6 C 0 = 1 way

4(4.5 x 1 block) and 3(3 x 1 block) --> 7 C 3 = 35 ways

2(4.5 x 1 block) and 6(3 x 1 block) --> 8 C 2 = 28 ways

0(4.5 x 1 block) and 9(3 x 1 block) --> 9 C 0 = 1 way

1 way + 35 ways + 28 ways + 1 way = 65 ways

As you can see here the number of ways is nowhere near 7958. What am I doing wrong here?

Also how would I find how many ways there are to construct a 48 x 10 panel? Because it's a little difficult to do it by hand especially when trying to find 7958 ways.

How would write a program to calculate an answer for the number of ways for a 7958 panel? Would it be easier to construct a program to calculate the result? Any help would be greatly appreciated.

Answer 1

Here's a solution in Java, some of the array length checking etc is a little messy but I'm sure you can refine it pretty easily.

In any case, I hope this helps demonstrate how the algorithm works :-)

import java.util.Arrays;

public class Puzzle
{
    // Initial solve call
    public static int solve(int width, int height)
    {
        // Double the widths so we can use integers (6x1 and 9x1)
        int[] prev = {-1};      // Make sure we don't get any collisions on the first layer
        return solve(prev, new int[0], width * 2, height);
    }

    // Build the current layer recursively given the previous layer and the current layer
    private static int solve(int[] prev, int[] current, int width, int remaining)
    {
        // Check whether we have a valid frame
        if(remaining == 0)
            return 1;

        if(current.length > 0)
        {
            // Check for overflows
            if(current[current.length - 1] > width)
                return 0;

            // Check for aligned gaps
            for(int i = 0; i < prev.length; i++)
                if(prev[i] < width)
                    if(current[current.length - 1] == prev[i])
                        return 0;

            // If we have a complete valid layer
            if(current[current.length - 1] == width)
                return solve(current, new int[0], width, remaining - 1);
        }

        // Try adding a 6x1
        int total = 0;
        int[] newCurrent = Arrays.copyOf(current, current.length + 1);
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 6;
        else
            newCurrent[0] = 6;
        total += solve(prev, newCurrent, width, remaining);

        // Try adding a 9x1
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 9;
        else
            newCurrent[0] = 9;
        total += solve(prev, newCurrent, width, remaining);

        return total;
    }

    // Main method
    public static void main(String[] args)
    {
        // e.g. 27x5, outputs 7958
        System.out.println(Puzzle.solve(27, 5));
    }
}