наибольший возможный прямоугольник букв

Напишите программу, которая находит максимально возможный прямоугольник букв, так что каждая строка образует слово (слева направо), а каждый столбец образует слово (сверху вниз).

Я нашел интересный вопрос. Это не домашнее задание, хотя может звучать так. (Я не в школе). Я делаю это для развлечения.

Пример

Из cat , car , ape , api , rep , ] tip получаем следующий прямоугольник (который является квадратом):

 car
а п е
кончик

Моя первоначальная идея - построить своего рода префиксное дерево, чтобы я мог извлекать все слова, начинающиеся с определенной строки. Это было бы полезно, когда у нас уже есть 2 или более слов (чтение сверху вниз или слева направо) и нам нужно найти следующее слово, которое нужно добавить.

Есть другие идеи?

Править

Можно ли это сделать с кубоидом (трехмерным прямоугольником)?

Что, если на диагоналях должны быть допустимые слова (автор идеи: user645466); как бы оптимизировать алгоритм для этого?