Для наибольшего числа выбираем цифры слева направо, каждый раз проверяя, можно ли после выбора использовать все цифры.

Число не может начинаться с 8: на шахматно раскрашенной таблице клетка с цифрой 8 принадлежит меньшему цветовому классу, а путь через все 9 клеток должен начинаться и заканчиваться клеткой большего класса.
Начало с 9 тоже невозможно. Если после 9 поставить 4, то выбор 8 приводит к тупику (ветви 9–4–8–3 и 9–4–8–1–6–5–2–7 не охватывают все цифры); выбор 6 также приводит к тупику (ветви через 8, 1 или 5 не охватывают все цифры); выбор 2 приводит к тупику через 7 либо через 5–6–1–8–3. Если после 9 поставить 3, далее вынужденно идёт 8; оба продолжения, через 1 или через 4, оставляют часть цифр неиспользованными.
Пробуем наибольшую возможную начальную цифру 7. Следующей выбираем 9, а затем 4. После 4 выбор 8 или 6 не позволяет пройти все клетки: например, из 8 продолжение через 3 сразу заходит в тупик, а продолжение через 1 вынуждает путь 6–5–2, где некуда перейти дальше. Ветви после 6 также не проходят через все цифры.
Поэтому после 7–9–4 выбираем 2. Далее 5 и 6 вынуждены. Из 6 выбираем 1, а затем 8 и 3.

Полученный путь по клеткам: 7–9–4–2–5–6–1–8–3. Все цифры использованы, соседние цифры стоят рядом по стороне.

Ответ: 794256183.

Поделись с друзьями