Алекс в стране чисел. Необычайное путешествие в волшебный мир математики - Беллос Алекс

Судоку

Кадзи поместил судоку в первых же номерах своего журнала головоломок, который начал выходить в 1980 году, но, по его словам, никто не обратил тогда на них никакого внимания. Лишь после того, как судоку пересекли границу Японии, они стали распространяться подобно лесному пожару.

Точно так же, как говорящие по-японски, но не знавшие английского люди могли понять, что требуется в головоломке «Поставь числа на место», говорившие по-английски, но не знавшие японского могли играть в судоку.

В 1997 году новозеландец по имени Уэйн Гоулд зашел в один из книжных магазинов в Токио. Увидев на полках только книги на японском языке, он поначалу слегка растерялся, но вдруг его глаз зацепился за что-то знакомое. Ему бросилась в глаза обложка книги, которая выглядела как кроссворд с расставленными в нем числами. Очевидно, это было нечто вроде головоломки, подумал он, но вот как она решается? Гоулд решил купить книжку и разобраться с ней потом. Во время отпуска, который он проводил на юге Италии, Гоулд наконец решил головоломку. Незадолго до того он вышел на пенсию — ранее он был судьей в Гонконге — и увлекся программированием на компьютере. Гоулд решил, что попробует написать программу, которая будет генерировать различные судоку. Программисту высшего класса для этого понадобилась бы пара дней, у Гоулда же на решение задачи ушло шесть лет.

Однако затраченные усилия стоили того, и в сентябре 2004 он смог убедить редакцию нью-гэмпширской газеты «Conway Daily Sun» опубликовать одну из своих головоломок. Успех превзошел все ожидания. В следующем месяце Гоулд решил попробовать силы в британской национальной прессе. Он полагал, что самый эффективный способ продвинуть свою идею состоит в том, чтобы предложить редакции готовый макет их газеты с уже помещенным в него судоку. Судебная практика в Гонконге многому его научила, так что изготовить хорошую подделку не составило большого труда. Он подготовил выглядевший достаточно убедительно «макет» приложения к «Times» и принес его с собой в главную редакцию этой газеты. Гоулду пришлось прождать несколько часов в приемной, но он все-таки сумел продемонстрировать свой самодельный номер кое-кому из сотрудников. Идея всем понравилась. Более того, не успел Гоулд уйти из редакции, как один из топ-менеджеров «Times» послал ему имейл с просьбой никому больше не показывать судоку. Первая головоломка была напечатана через две недели, а уже через три дня газета «Daily Mail» предложила свой собственный вариант. В январе 2005 года в игру вступила и «Daily Telegraph». Прошло совсем немного времени, и уже каждая британская газета считала своим долгом ежедневно публиковать подобную головоломку, чтобы не отставать от конкурентов. В тот год, по данным газеты «Independent», продажи карандашей в Великобритании возросли в 7 раз — по мнению газеты, это было связано с массовым помешательством на судоку. К лету в книжных магазинах, газетных киосках и в аэропортах появились отдельные полки со сборниками судоку, причем это наблюдалось не только в Соединенном Королевстве, но и по всему миру. По данным «USA Today» в 2005 году шесть из 50 наиболее популярных книг в списке бестселлеров были книгами по судоку. К концу года судоку распространились уже в 30 странах, а журнал «Time» назвал Уэйна Гоулда в числе 100 наиболее влиятельных людей года — он оказался в этом списке в компании Билла Гейтса, Опры Уинфри и Джорджа Клуни. К концу 2006 года головоломки судоку публиковались в 60 странах, а к концу 2007-го — в 90. По оценкам Маки Кадзи, число людей, регулярно решающих судоку, превышает ныне 100 миллионов.

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

Например, как только вы поняли правила судоку, становится полностью ясной идея единственности решения. Для каждой числовой структуры в таблице имеется только одно возможное окончательное расположение для чисел в пустых клетках. Однако при этом не верно, что всякая частично заполненная таблица будет иметь единственное решение. Вполне может случиться, что некий квадрат 9 × 9 с расставленными в нем числами не имеет решения, как может случиться и то, что у данного квадрата будет много решений. Когда британский спутниковый канал «Sky TV» запустил Судоку-шоу, продюсеры нарисовали таблицу размером 275 на 275 футов на известняковом холме, расположенном где-то в сельской местности в Англии. Это, по их утверждению, было самое большое судоку в мире. Однако предложенные ими числа позволяли заполнить квадрат 1905 различными способами. Таким образом, разрекламированное самое большое судоку не имело единственного решения, а потому и не могло классифицироваться как судоку.

Область математики, имеющая дело с перечислением комбинаций (таких, например, как упомянутые 1905 решений фальшивого судоку, предложенного «Sky TV»), называется комбинаторикой. Она состоит из изучения перестановок и комбинаций предметов, подобных числам из таблицы. Кроме того, к комбинаторике относится и знаменитая задача о коммивояжере. Пусть, скажем, я — коммивояжер, и мне надо заехать в 20 магазинов. В каком порядке мне надо в них заезжать, чтобы полный путь, который я проделаю, оказался минимальным? Решение требует рассмотрения всех перестановок путей между всеми магазинами, и представляет собой классическую (и исключительно сложную) комбинаторную задачу. Подобные задачи постоянно возникают в бизнесе и промышленности; например, при составлении расписания вылета самолетов из аэропорта или при проектировании эффективной системы сортировки почты.

Комбинаторика — это область математики, которая имеет дело с исключительно большими числами. Как мы видели на примере магических квадратов, уже небольшое количество чисел можно расположить на удивление большим количеством способов. Хотя и латинские, и магические квадраты образуют квадратные таблицы, при их одинаковом размере латинских квадратов меньше, чем магических, однако латинских квадратов все равно очень много. Например, количество латинских квадратов размером 9 × 9 выражается числом из 28 цифр. Сколько среди них различных судоку? Число латинских квадратов, представляющих собой судоку, — то есть таблиц размером 9 × 9, в которых 9 подквадратов содержат все цифры, — меньше полного числа примерно в сто тысяч раз и равно 6 670 903 752 021 072 936 960. Впрочем, многие из этих таблиц представляют собой различные варианты одного и того же квадрата, получаемые отражением или вращением (что мы видели выше для магического квадрата 3 × 3). Если не считать квадраты, получаемые вращениями и отражениями, то искомое количество заметно уменьшается: общее число различных возможностей для целиком заполненных таблиц судоку оказывается равным примерно 5,5 миллиарда.

Это, впрочем, не равно полному числу возможных судоку, которое намного больше данного числа, потому что каждая заполненная сетка будет решением многих разных судоку. Скажем, напечатанное в газете судоку имеет одно-единственное решение. Но как только вы заполните один из квадратов, вы немедленно тем самым создадите новую таблицу с новым набором данных, другими словами — новое судоку с тем же единственным решением, и т. д. для каждого из квадратов, которые вы будете заполнять. Так что если в данном судоку имеется, скажем, 30 исходно заданных чисел, то у вас есть возможность создать еще 50 других судоку с тем же единственным решением — до тех пор, пока не будет заполнена вся таблица. (Это означает новое судоку для каждого дополнительного числа, до тех пор пока в таблице из 81 квадрата не окажется 80 заполненных.) Нахождение полного числа судоку не слишком интересно, поскольку большинство таблиц для них имеют лишь очень небольшое число незаполненных клеток, что не отвечает духу этих головоломок. Математиков гораздо более привлекает задача нахождения минимального числа цифр, исходно расставленных по таблице. Самый главный комбинаторный вопрос касательно судоку звучит так: каково наименьшее количество чисел, которые можно оставить, чтобы имелся только один способ заполнения всей таблицы?