Cover The Wall With Square Tiles

Firstly, observe all the measurements are divisible by 9 inches, so divide by that. Now the red tiles are 1x1, the blue tiles 2x2 and the green tiles 3x3. The stove space to be tiled is 3x9 . Much neater!

Polya said: if you can't solve a problem, start by solving a simpler problem. Let f(n) be the number of ways of tiling a 3 x n space.

Experiment on paper, draw out all combinations. Find that f(1) = 1, f(2) = 3, f(3) = 6 and f(4) = 13

Stop and think. There's a recurrence relation for f. Given any 3 x n tiling, consider the rightmost column. Either the right most column is (a slice of) a 3x3 tile, or it contains a 2x2 tile, or it is exactly three 1x1 tiles. Thus

$f(n) = f(n-3) + 2 f(n-2) + f(n-1)$

The middle term is doubled because there are two ways to cover a 3x2 space with a 2x2 tile and two 1x1s.

Compute (on paper or Python) f(9) = 595

using recursive function in python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

c=0;
m=[[False for j in xrange(0, 9)] for j in xrange(0, 3)]

def full():
    for i in xrange(0, 3):
        for j in xrange(0, 8):
            if not m[i][j]:
                return False

    return True

def set(x, y, s):
    tx=x-s+1
    ty=y-s+1

    if tx<0 or ty<0:
        return False

    for i in xrange(tx, x+1):
        for j in xrange(ty, y+1):
            if m[i][j]:
                return False

    for i in xrange(tx, x+1):
        for j in xrange(ty, y+1):
            m[i][j]=True

    return True

def unset(x, y, s):
    tx=x-s+1
    ty=y-s+1

    for i in xrange(tx, x+1):
        for j in xrange(ty, y+1):
            m[i][j]=False

def f(i, j):
    global c
    if j<0:
        if i>0:
            f(i-1, 8)

        else:
            if full():
                c+=1
        return

    if m[i][j]:
        f(i, j-1)
    else:
        for s in xrange(1, 4):
            if set(i, j, s):
                f(i, j-1)
                unset(i, j, s)

f(2,8)
print c