Одним из величайших достижений Эйлера стала разработка алгоритмического мышления. Отличительная особенность эйлеровских алгоритмов состояла в том, что они предназначались для решения проблем, казавшихся неразрешимыми. Одной из таких проблем было высокоточное предсказание фаз Луны — информация о фазах Луны имела жизненно важное значение для составления таблиц, необходимых для мореплавания. Еще Ньютон показал, что можно сравнительно легко предсказывать орбиту одного тела, обращающегося вокруг другого, но в случае Луны ситуация не столь проста.

Луна обращается вокруг Земли, но третье тело — Солнце — существенно усложняет картину. Земля и Луна притягивают друг друга, а Солнце возмущает положение Земли и сталкивает Луну с ее идеальной орбиты вокруг Земли. Уравнения позволяли описать поведение Земли и Луны, но математики XVIII века не умели учитывать в своих вычислениях влияние третьего тела. Даже сегодня невозможно предсказать, как будет вести себя точное решение этой задачи (класс таких задач называется «задачей трех тел»). Эйлер понял, что мореплавателям нет необходимости знать фазу Луны с абсолютной точностью — вполне достаточно такой точности, которая позволяет определить положение судна с точностью до нескольких морских миль. И он разработал рецепт, позволяющий получать не идеальное, а достаточно точное решение. Такой рецепт, называемый алгоритмом, позволяет получить сначала весьма приближенное, грубое решение. Затем это решение можно ввести в качестве исходных данных в тот же алгоритм и получить уже более точное решение. В свою очередь, уточненное решение, если его также ввести в алгоритм, порождает еще более точное решение, и т. д. После ста или около того итераций Эйлер получил возможность определить положение Луны с точностью, достаточной для нужд мореплавания. Свой алгоритм Эйлер представил британскому Адмиралтейству и получил награду в триста фунтов стерлингов.

Эйлер заслужил репутацию человека, способного решить любую поставленную ему задачу, причем не только математическую. В бытность свою при дворе Екатерины Великой он встретил великого французского философа Дени Дидро. Тот был убежденным атеистом и пытался обратить в атеизм представителей русской знати. Разгневанная этим Екатерина обратилась к Эйлеру с просьбой пресечь деятельность французского безбожника.

Эйлер поразмыслил над просьбой императрицы и объявил, что располагает алгебраическим доказательством существования Бога. Екатерина Великая пригласила Эйлера и Дидро во дворец и собрала на теологический спор всех придворных. Эйлер встал перед аудиторией и заявил:

«Сир! (a + bn )/n = x , следовательно Бог существует. Что Вы имеете возразить?»

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

Более «земная» задача, привлекшая внимание Эйлера, большого любителя головоломных проблем, связана с прусским городом Кёнигсбергом (ныне — российский город Калининград). Город стоит на берегах реки Прегили и состоит из четырех частей, соединенных между собой семью мостами. План города схематически изображен на рис. 7. Некоторые из любопытных жителей Кенигсберга заинтересовались, можно ли обойти все семь мостов, не переходя ни по одному из них дважды. Кое-кто из обитателей Кенигсберга попытался проложить различные маршруты, но ничего хорошего из этого не вышло. Эйлеру также не удалось обойти все семь кёнигсбергских мостов, побывав на каждом только один раз, но зато он сумел объяснить, почему сделать это невозможно.

Рис. 7. Река Прегиль делит Кёнигсберг на четыре несвязанные части A, B, C и D. Различные части города соединены между собой семью мостами. Можно ли обойти все семь мостов побывав на каждом один и только один раз?

Рис. 8. Упрощенная схема семи кёнигсбергских мостов

Эйлер взял план города и заменил его упрощенной схемой, на которой части города изображены точками (узлами), а мосты — линиями (ребрами), как на рис. 8. Затем Эйлер стал рассуждать так. Чтобы существовал маршрут, позволяющий обойти ровно по одному разу все мосты, каждая точка на схеме должна принадлежать четному числу линий. Это связано с тем, что в середине обхода путешественник, проходя какую-то из частей города, должен войти в нее по одному мосту, а выйти — по другому. Из этого правила существуют лишь два исключения: когда путешественник начинает или завершает обход. В самом начале обхода путешественник покидает некую часть города, и для выхода из нее необходим только один-единственный мост. Если обход начинается и заканчивается в различных частях города, то число мостов, ведущих к каждой из них нечетно. Но если обход начинается и заканчивается в одной и той же части города, то соответствующая ей точка на схеме, как и все другие точки, должна принадлежать четному числу линий (т. е. эта часть города должна быть соединена с другими частями четным числом мостов).