Поиск с возвратом

[Filin_]

Всем приятного времени суток!! Подскажите пожалуйста идею алгоритма поиска с возвратом для решения такой задачи: дан квадрат (сторона длиной L условно), нужно найти минимальное (по количеству кусков) разбиение на квадраты со стороной от 1 до L-1. Куски (ну то есть квадратики) могут повторяться.

[FPaul]

Это похоже на "Представить число N суммой минимального количества квадратов". В общем-то, "правильный" алгоритм решения - динамическое программирование - вариант алгоритма Дейкстры.

Ваш метод - поиск с возвратом.
Смысл поиска с возвратом - обычный перебор в нескольких вложенных циклах for. Т.к. точное количество вложений циклов заранее не известно, их имитируют тем или иным способом, например, рекурсией.
Чтобы сократить перебор, при достижении невыполнимых условий завершают текущий уровень рекурсии и "наверх" передают результат "нет ответа", т.е. "не запоминать" значение переменной цикла, как найденное решение.

Для задачи в такой постановке

Сообщение от Filin_

дан квадрат (сторона длиной L условно), нужно найти минимальное (по количеству кусков) разбиение на квадраты со стороной от 1 до L-1. Куски (ну то есть квадратики) могут повторяться.

оцениваю максимальное количество слагаемых в 5 из следующих соображений:
Теорема Лагранжа о сумме четырёх квадратов
позволяет оценить число слагаемых не более 4 с учётом слагаемых, равных L^2.
Для данной задачи это неприемлемо. Тогда поступим так, возьмём первое слагаемое (первый квадрат) со стороной (L-1) и получим, что осталось представить в виде суммы квадратов число
(L)^2-(L-1)^2=(L+L-1)(L-L+1)=(2L-1)
И на это число уже не распространяется ограничение о невозможности представления одним слагаемым в случае, когда (2L-1) является полным квадратом. И, согласно теореме, (2L-1) можно представить суммой не более 4 квадратов.
Получаем, что максимальное количество слагаемых для представления числа (L)^2 не превышает 5.
Это число - 5 - пригодится для ограничения глубины рекурсии (ну или количества вложенных циклов - в других терминах).

Пусть в рекурсивную функцию поступает параметр S - сумма, которую нужно выразить через слагаемые. В рекурсивной функции организуете цикл i от sqrt(S) до 1, и вызываете рекурсию f(S-i*i). Добавляете проверки, чтобы на входе не было отрицательных чисел, ещё какие-нибудь.
В случае, когда на входе S==0, запоминаете в глобальной переменной результат.

[FPaul]

Нет, я ошибся.
Это не арифметическая задача, а задача на разрезание исходной фигуры.
Нужно несколько иное решение.