Как написать сложный алгоритм?

Вопрос не достаточно конкретизирован. Но я рискну предположить, что автор имеет ввиду следующее:

Пусть задан набор слов из N:

w_0
w_1
...
w_N

Пусть задано число M (== 16). Необходимо найти такие номера слов, что их суммарная длина будет равна M.

Перейдём к решению.

Для начала, заметим, что слова, как объекты нас не интересуют. Нам интересны лишь их длины. Длины их обозначим через l_i. Т.е. теперь у нас есть последовательность длин слов (их даже следует назвать множеством):

X = {l_0, l_1, ..., l_N}

Математически строго поставим задачу (к решению имеет косвенное отношение).

В таком случае, нам нужно понять, существует ли решение хотя бы одного уравнения A_k над нашим множеством X:

A_k: x_0 + x_1 + x_2 + ... + x_k = M

Т.е. существует ли решение уравнения

x0 = M

или

x_0 + x_1 = M:

или

...

x_i может принимать значения из множества X ограниченное число раз.

Продолжение решения

Нам нужно найти комбинацию l_i, которые в сумме дадут M.

Отсортируем последовательность l_0, ..., l_i, ..., l_N по убыванию и выбросим все те l_i > M, так как они не смогут участвовать в финальной сумме. После сортировки имеем:

s_0, s_1, ..., s_p,

где s_i <= M, s_i >= s_{i+1}.

Теперь нам нужно перебрать все варианты решения (т.к. M=16, т.е. небольшое, то мы в полне уложимся в перебор). Для перебора будем использовать DFS.

Как мы это будем делать. Выберем s_0 попробуем подобрать для него такое число s_i (i >= 0), что s_0 + s_i <= M. Если s_0 + s_i = M, то решение найдено. Если нет, то продолжаем поиск. Т.е. выберем для s_i такое s_j (j >= i), что s_0 + s_i + s_j <= M.

На некотором шаге может оказаться, что s_0 + s_i + s_j >= M. В таком случае дальше осуществлять перебор не имеет смысла. Необходимо вернуться на предыдущий шаг и найти s_k (k > j). Т.е. подобрать s_0 + s_i + s_k <= M. Если мы перебрали все возможные варианты, но не нашли сумму такую, что она равна M, то решения нет.

Для большего понимания, как следует организовать перебор, приведу псевдокод:

def dfs(s, sum):
    for number in get_next_number(s):
        new_sum = sum + number
        answ = False
        if new_sum == m: # Если нашли решение, то выходим из перебора
            return True
        elif new_sum < m: # Если решение не нашли, то пытаемся взять следующее число и повторить итерацию
            answ = dfs(number, new_sum)
        if answ:
            return True
    return False # Если ни в одном случае не удалось подобрать сумму, то выходим

dfs нужно запустить от каждого из имеющихся чисел s.

Точно сложность не могу оценить, но дам верхнюю оценку. Она точно не больше O(N^3) по времени. Но следует понимать, что это завышенная оценка. Скорее всего, реальное время работы будет близко к O(N^2) или даже O(N log N)

Я также предполагаю, что можно предложить более умное решение динамическим программированием, в частности, свести эту задачу, к задаче о рюкзаке.

Другой вариант решения был предложен в комментариях. Для этого достаточно каждому слову поставить в соответствие метку 1 или 0, которая будет обозначать: нужно ли брать в ответ слово или не нужно. Таким образом, мы имеем битовую маску, состоящую из 0 и 1. Нам необходимо перебрать все возможные комбинации (их 2^N), посчитав для каждой из них суммарную длину выбранных слов.

Приведу пример:

один // длина 4

два_ // длина 4

пять // длина 4

три // длина 3

четыре // длина 6

Пусть M = 12.

Маска будет состоять из 5 битов. Будем начинать перебор с маски 00000:

10000. Слова: один. Суммарная длина4 != M 01000. Слова:два_.Суммарная длина 4 != M 11000. Слова: один, два_. Суммарная длина8 != M 00100. Слова:пять. Суммарная длина4 != M 10100. Слова:один,пять. Суммарная длина8 != M 11100. Слова:один,два_,пять. Суммарная длина12 == M`

В ответ могут войти слова: [один, два_, пять]

Спешу заметить, что вычислительная сложность алгоритма велика: O(2^N). Т.е. уже при 30 словах вы получите достаточно долго работающий алгоритм (минута или более).

Что касается сетки, то для задания её размеров можно задавать A, B -- размеры её сторон. По этим величинам вы генерируете саму сетку. A * B = M

Для расположения слов, согласно вышеописанному алгоритму, можно воспользоваться "зейкой". Вы перебираете последовательно ячейки и кладёте туда по одной букве. Предварительно, разумеется, следует расположить все слова друг за другом:

words = 'одиндватричетыре'
letters_count = 0
for x in range(0, A):
   if x % 2 == 0:
      line = range(0, B)
   else: 
      line = range(B, 0, -1)
   for y in line:
      matrix[y][x] = words[letters_count]
      letters_count += 1