Если он сумел построить их в одно каре, то это число - квадрат, и 125 не подходит.
Дальше, он построил несколько каре 4*4 (16 чел) и одно 5*5 (25 чел).
Значит, если из числа солдат вычесть 25, останется число, кратное 16.
n - 25 = 16k.
Числа, кратные 16: 16, 32, 48, 64, 80, 96, 112, 128
Больше 128 брать нет смысла, потому что 128+25=153>150
Из всех чисел подходит только 96+25=121
Ответ: 121 солдат, сначала встали в каре 11*11, потом в 6 каре 4*4 и одно 5*5.