Tiling Dominoes and Trominoes on a 2xN Grid

Problem Overview

• Goal: Find the number of ways to tile a 2xN rectangle grid using 2x1 dominoes and L-shaped trominoes.
• Constraint: N is an integer between 1 and 1000.
• Result: Return the answer modulo $10^9 + 7$.

Observations

• Though two types of tiles increase complexity, the grid's thinness (2xN) simplifies the problem.
• Example Solutions:
  • For N=1: Exactly 1 solution.
  • For N=2: Exactly 2 solutions.
  • For N=3: Exactly 5 solutions.
  • For N=4: Exactly 11 solutions.

Hints for Solving

1. Track Column Index: Keep track of the column index in the DP state.
2. Column Slice: Identify the number of possible states arising from one column slice.

Approach

Dynamic Programming (DP) State Representation

• Tile the grid fully from left to right without gaps.
• Column States:
  • State 0: Neither row is tiled.
  • State 1: Top row is tiled.
  • State 2: Bottom row is tiled.
  • State 3: Both rows are tiled.

Recursive Transitioning

• Track partial states up to a certain index.
• Use dominoes and trominoes to transition between states without leaving gaps.

State Components

1. Index (i): Position up to which the board is fully tiled.
2. Column State: Configuration of the last column.

Frontier Tiles

• Frontier Tiles (T1, T2, T3, T4): Available tiles on the extremity of the current state.

Placing Tiles

• Check availability of frontier tiles before placing a domino or tromino.
• Update frontier based on placed tiles.

Pseudocode

mod_val = 10**9 + 7
n = (length of the board given as input)
dp = [[None] * 4 for _ in range(n+1)]

# Solve function

solve(n):
    return f(0, True, True)

# Recursive function f

def f(i, t1, t2):
    if i == n:
        return 1
    state = make_state(t1, t2)
    if dp[i][state] is not None:
        return dp[i][state]
    t3 = t4 = (i + 2 <= n)
    count = 0
   
    # Place L-shaped or horizontal tiles based on availability
    if t1 and t2 and t3:
        count += f(i + 2, False, True)
    if t1 and t2 and t4:
        count += f(i + 2, True, False)
    if t2 and t3 and t4:
        count += f(i + 2, True, False)
    if t1 and t2:
        count += f(i + 1, True, True)
    if t3 and t4:
        count += f(i + 1, False, False)
    if t2:
        count += f(i + 1, True, False)
    if t1:
        count += f(i + 1, False, True)

    dp[i][state] = count % mod_val
    return dp[i][state]

# Function to encode column state into a number

def make_state(t1, t2):
    return int(t2) * 2 + int(t1)

Conclusion

• Explored tiling a 2xN grid using both iterative (previous video) and recursive approaches.
• Emphasized on capturing partial states and ensuring no gaps are left in the grid.

Call to Action

• Like the video if you learned something new.
• Subscribe for more content.