Придет Solmir и окажется, что есть значительно более элегантное решение. 
Особо элегантного не будет.
Два важных момента уже отметили:
1) средняя (пятая) цифра это 5,
2) чередуются нечетные и четные цифры.
Менее важно, но отметили: деление всего числа на 9 обеспечено автоматически.
Добавлю.
3) При делении на 4 мы имеем число вида ****, если отметить четные и нечетные цифры, то получаем нчнч=нч*100+нч. Последнея цифра должна быть 2 или 6, иначе нчнч не разделится на 4. Аналогично покажем, что второе из чисел 2 или 6 должно стоять на 8 месте.
Имеем выбор между нчн25чн6н и нчн65чн2н.
4) Рассмотрим первые 3 цифры нчн. среди цифр нет 2.5,6. Сумма цифр равна N. Число делится на 3 (по условию) и на 2, значит и на 6. N делится на 6 и может быть равно 12 или 18 (N=6 требует цифры 2, но она "заиграна", N=24 требует 9,8,7, то есть остается выбор между 987 и 789).
5) Число нчн25ч или нчн65ч делится на 6. При этом первые три цифры образуют число, которое делится на 3. Значит 25ч или 65ч тоже делится на 3. Отсюда варианты цифр с 4-й по 6-ю: 258 и 654.
Варианты нчн (их сумма 12 или 18)258н6н или нчн654н2н. Но число четных цифр ограничено. Выбор между н4н258н6н и н8н654н2н.
И так далее. Получаем перебор, но не очень большой.
