Calculating the number of tilings of a rectangle by smaller rectangles?

Question

Algorithms

Hello!
Let's say we have a big rectangle.
There is also an unlimited bunch of small identical rectangles, with an aspect ratio of 2:1, for example 100x50.
It is necessary to calculate and fix all the ways of tiling a large rectangle with small ones, so that they do not go beyond the edges of the large one and are tightly pressed against each other.
Let us also know in advance that a large rectangle can be tiled in at least one way.
I am attaching a picture (for example, two tiling options).

What are the algorithms for this? Which way to look?

Answer 1

Enumerating with the help of recursion is enough here.
You need to fill an M*N rectangle with 1*2 tiles.
Take the array A[M,N], fill it with zeros.
Call the Fill(A,1) function.
Fill(A,k){
Looking for the first element of A[p,q] equal to zero.
If not found - the array is full, print it. return.
If the element A[p+1,q] exists and is equal to zero, then you can put a horizontal tile in the rectangle: put the number k in A[p,q] and A[p+1,q], call Fill(A,k+ one). Zero out A[p,q] and A[p+1,q].
If the element A[p,q+1] exists and is equal to zero, then a vertical tile can be placed in the rectangle: in A[p,q] and A[p,q+1] put the number k, call Fill(A,k+ one). Zero out A[p,q] and A[p,q+1].
}
If you had to count the number of ways to fill, you would have to look towards dynamic programming.