Tiling a 4xN board with L shaped 3x2 tiles

Question

I need to find the number of the possible combinations of tilings of a 4xN board, with L shaped tiles that are 3x2. The tiles can be rotated freely. Any solution? Thanks.

Answer 1

I have a sollution which involves backtracking.

Order the squares in the grid like this: $$ \begin{matrix} 1 & 5 & 9 & \ldots \\ 2 & 6 & 10 & \ldots \\ 3 & 7 & 11 & \ldots \\ 4 & 8 & 12 & \ldots \\ \end{matrix} $$

Figure out all the ways to occupy the least square (the one with the smallest number I just assigned), there might be more ways to do that. You can also check it you don't create a gap which would be then impossible to fill to speed the algorithm. Iterate over all the possible ways to occupy the least square and for each way calculate the number of possibilities to tile the rest. After that, sum these numbers up and you get the result.

You will also need to cache the results because you will be filling the same space many times again. The cache should grow by $O(N)$ because there are only constantly many ways the untiled area can border with the tiled area. The border will never exceed the size 3×4 because the ordering ensures that the gaps in the border must be filled before the border moves to the right.

No combination will be explored twice because each combination is defined by the sequence of rotations of tiles in the least square.

Pseudo-code:

int Tile(shape_of_uncovered_region) {
  if (shape_of_uncovered_region is in cache) then return extract_from_cache(shape_of_uncovered_region)
  sum = 0
  least_square = find the unoccupied square with the least number
  for (new_tile in (all ways to occupy least_square by a new tile)) {
      if (is obvious that it will be impossible to finish tiling) then continue //optional
      sum += Tile(shape_of_uncovered_region without new_tile)
  }
  put (shape_of_uncovered_region, sum) into cache
  return sum
}