from copy import deepcopy
from typing import List
# https://[Log in to view URL]
def solve(X, Y, solution=[]):       
    if not X:
        yield list(solution)
    else:
        c = min(X, key=lambda o: len(X[o]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            for s in solve(X, Y, solution):
                yield s
            deselect(X, Y, r, cols)
            solution.pop()


def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].remove(i)
        cols.append(X.pop(j))
    return cols


def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)

def fit_bag(height: int, width: int, items: List[List[List[int]]]) -> List[List[int]]:
    
    Y = {}
    hsh = {}
    for i, _item in enumerate(items):
        item = [it for it in _item if any(x != 0 for x in it)]
        n, m = len(item), len(item[0])
        j = next(y for y in range(m) if item[0][y] != 0)
        idx = item[0][j]
        print("idx :", idx, item)
        k = 0
        for x in range(height - n + 1):
            for y in range(width - m + 1):
                key = chr(64 + idx) + str(k)
                values = [(x + u) * width + y + v for u in range(n) for v in range(m) if item[u][v] != 0]
                # to differentiate identical pieces in different locations
                # and prevent multiple use of same piece for exact cover problem
                values.append(width * height + i)
                Y[key] = values
                k += 1

    print("Y:", Y)
    X = {j: set() for j in range(width * height + len(items))}
    for i in Y:
        for j in Y[i]:
            X[j].add(i)  
    print("X:", X)
    print(len(X))
   
    _Y = {}
    for key, lst in Y.items():
        _Y[key] = lst[:]
    ans = [[None for _ in range(width)] for _ in range(height)]
    for sol in solve(X, Y, solution = []):
        print("sol :", sol)

        for c in sol:
            idx = ord(c[0]) - 65
            for v in _Y[c]:
                # the condition leads to a real point inside rectangle
                if v < width * height:
                    x, y = divmod(v, width)
                    ans[x][y] = idx + 1
        return ans

h, w = 3, 8
items = [
    [
      [1, 1, 1, 1],
      [1, 0, 0, 0],
      [1, 0, 0, 0]
    ],
    [
      [2, 2, 0],
      [0, 2, 0],
      [2, 2, 2],
    ],
    [
      [3, 3],
      [3, 3],
      [0, 3],
    ],
    [
      [4, 4, 4, 4],
      [4, 4, 4, 0],
    ]
]
r = fit_bag(h, w, items)
print(r)