Рекурсивный бэктрэкинг

Написал решение для данной задачи: Найди решение этой задачи в интернете Рекурсивный бэктрекинг. Напиши полный код На pythonУ Вовы много квадратных обрезков доски. Их стороны (размер) изменяются от 1 до N−1, и у него есть неограниченное число обрезков любого размера. Но ему очень хочется получить большую столешницу - квадрат размера N . Он может получить ее, собрав из уже имеющихся обрезков(квадратов).Например, столешница размера 7×7 может быть построена из 9 обрезков.

Внутри столешницы не должно быть пустот, обрезки не должны выходить за пределы столешницы и не должны перекрываться. Кроме того, Вова хочет использовать минимально возможное число обрезков. Входные данные Размер столешницы - одно целое число N (2≤N≤20). Выходные данные Одно число K, задающее минимальное количество обрезков(квадратов), из которых можно построить столешницу(квадрат) заданного размера N. Далее должны идти K строк, каждая из которых должна содержать три целых числа,x,y и w, задающие координаты левого верхнего угла ( 1≤x,y≤N) и длину стороны соответствующего обрезка(квадрата).

Пример входных данных 7 Соответствующие выходные данные 9 1 1 2 1 3 2 3 1 1 4 1 1 3 2 2 5 1 3 4 4 4 1 5 3 3 4 1

def find_min_squares(n):
    board = [[0]*n for _ in range(n)] # Создаем столешницу размера N x N

    # Функция для проверки, можно ли поставить квадрат размера size на доску
    def can_place(x, y, size):
        if x+size > n or y+size > n: # Проверяем, выходит ли квадрат за пределы столешницы
            return False
        for i in range(x, x+size):
            for j in range(y, y+size):
                if board[i][j] != 0: # Проверяем, свободно ли место
                    return False
        return True

# Функция для размещения квадрата на доске
    def place(x, y, size, id):
        for i in range(x, x+size):
            for j in range(y, y+size):
                board[i][j] = id

# Функция для удаления квадрата с доски
    def remove(x, y, size):
        for i in range(x, x+size):
            for j in range(y, y+size):
                board[i][j] = 0

# Рекурсивная функция для поиска минимального количества квадратов
    def backtrack(x=0, y=0, next_id=1):
        if y >= n: # Если y выходит за пределы, переходим на следующую строку
            x += 1
            y = 0
        if x >= n: # Если все клетки заполнены, возвращаем True

            return True
        if board[x][y] == 0:  # Если текущая клетка свободна
            for size in range(n-1, 0, -1):  # Пробуем разместить квадраты всех возможных размеров
                if can_place(x, y, size):
                    place(x, y, size, next_id)
                    if backtrack(x, y + size, next_id + 1):
                        return True
                    remove(x, y, size)  # Бэктрекинг, если не найден подходящий квадрат
            return False  # Если не удалось разместить ни одного квадрата
        return backtrack(x, y + 1, next_id)  # Переходим к следующей клетке


    # Вывод результатов
    def get_results():
        squares = []
        for id in range(1, n ** 2 + 1):
            found = False
            for i in range(n):
                for j in range(n):
                    if board[i][j] == id:
                        size = 1
                        while i + size < n and board[i + size][j] == id:
                            size += 1
                        squares.append((i + 1, j + 1, size))
                        found = True
                        break
                if found:
                    break
        return [len(squares)] + squares

    # Запускаем поиск
    if backtrack():
        return get_results()
    else:
        return "Решение не найдено."

n = int(input())
results = find_min_squares(n)
print(results[0])
for result in results[1:]:
    print(*result)

Но он не находит минимальное количество, помогите исправить.