Судоку: магия чисел
Кубик-рубика имеет сложную конструкцию, для игры в шахматы нужны фигурки и доска, для многочисленных карточных игр необходимы колоды карт разного объёма, для древнейшей игры в кости требуются аккуратно изготовленные кубики. И только для игры в судоку не нужно ничего, кроме листа бумаги и карандаша.
Продвинутая бабушка
Прежде чем перейти к обсуждению непосредственной темы этой статьи, представим себе небольшую сценку из жизни. Обычный среднестатистический российский город. Рядом с перекрёстком двух проспектов стоит газетный киоск типа «Союзпечать». Ассортимент киоска — стандартный для подобных точек розничной торговли по всей стране: журналы, газеты, мелкая канцелярия, бульварное чтиво, сувениры, китайские игрушки. К киоску не спеша подходит пожилая интеллигентная дама. Наклонившись к низкому окошку, она требует свежий номер журнала с задачами судоку за эту неделю (заметьте, именно еженедельный, значит это действо повторяется неоднократно), получает желаемое, внимательно разглядывает, а затем (внимание!) возвращает книжечку обратно со словами: «Нет, пожалуйста, дайте другие, повышенной сложности: эти слишком простые». Ай да бабушка! Она не просто разгадывает судоку, но и является настоящим гуру, требующим задачки посложнее.
Судоку уже давно не является экзотикой и развлечением для узколобых интеллектуалов. По популярности эта головоломка стремительно приближается к кроссвордам. Причём судоку — это именно головоломка, заставляющая думать, в отличие от кроссворда, который по большому счёту является лишь тестом на эрудицию и словарный запас. Бабушка-гуру ярко и наглядно продемонстрировала, что в нашей стране судоку стала по-настоящему народной игрой. Раньше, видя в метро человека, склонившегося над журнальной страницей и задумчиво грызущего ручку, мы почти безошибочно определяли, что он разгадывает кроссворд. Теперь мы, скорее всего, подумаем, что он разгадывает судоку.
Программа на ближайшие выходные
Правила
Для тех, кто не в курсе, что такое судоку, кратко опишу правила этой головоломки. Много места для этого не потребуется. Дан квадрат 9 на 9 клеток, в часть клеток уже вписаны цифры от 1 до 9. Необходимо заполнить остальные клетки, соблюдая правило: в каждой строке, в каждом столбце и в каждом малом квадрате 3 на 3 каждая цифра от 1 до 9 должна встречаться только один раз. Вот, собственно, и вся головоломка.
Сложность головоломки зависит от количества заранее расставленных цифр и их размещения. В мире судоку принято выделять четыре уровня сложности: простой, промежуточный, сложный и очень сложный. Простые головоломки решаются путём несложного сопоставления чисел. Судоку на промежуточном уровне может потребовать выполнения в уме некоторых расчётов. Сложный же уровень, скорее всего, потребует глубокого анализа и, как говорил мой институтский профессор по высшей математике, «многочасового домашнего обдумывания».
История успеха
Официально датой рождения судоку в её классическом виде считается май 1979 года. В этом году головоломка впервые была опубликована в журнале Dell Magazines под именем Number Place. Автором этой головоломки был американский архитектор из Индианы Говард Гарнс (Howard Garns). Первая головоломка судоку была нарисована Говардом на чертёжной доске для собственного развлечения. Кстати, ему в это время уже было за 70. Как это часто бывает, при первой публикации имя автора где-то затерялось и головоломка вышла на страницах журнала анонимной. Имя Говарда указывалось только в общем списке авторов журнала, напечатанном мелким шрифтом, всякий раз, когда головоломка появлялась на страницах журнала.
Говард Гарнс разгадывает своё изобретение
Однако настоящую популярность головоломка обрела в 1984 году в Японии. Именно тогда она появилась на страницах японского журнала головоломок Nikoli. Тогда же появилось и само слово «судоку». Оно состоит из двух иероглифов: «су» и «доку», что в переводе с японского означает «числа рядом». Вообще, «судоку» — это сокращение от более длинного «Suuji wa dokushin ni kagiru» («число может использоваться только один раз»). Интересно, что в самом японском издании по поводу истории головоломки написано только то, что она была позаимствована «в американском журнале головоломок».
Расшифровка слова «судоку»
2 ноября 2004 года головоломка впервые появилась на страницах культовой британской газеты The Times. А уж то, что появилось на страницах «Таймс», становится известным всей Европе, а затем и всему миру. Головоломка судоку начала своё победное шествие по планете. За короткое время судоку заполонили буквально всю Америку: их можно было увидеть в самолётах, автобусах, в офисах. Судоку из The New York Times вырезались, ксерокопировались, рассылались по почте (обычной, а не электронной). Мир охватила настоящая «судокумания».
Магические предки
Иногда судоку по старой памяти (и не совсем правильно) называют «магическим квадратом». Однако на это есть веские причины. Дело в том, что сам принцип заполнения квадрата числами по указанному правилу известен ещё с глубокой древности. В общем математическом смысле это квадрат n на n клеток, заполненных числами (любыми, а не только от 1 до 9) таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях является одинаковой.
Головоломки, подобные судоку, начали появляться в прессе ещё в 19 веке. Например, в 1892 году во французской газете Le Siecle публиковались головоломки, основанные на магическом квадрате, которые в строгом смысле судоку не являлись.
В судоку реализован так называемый нормальный магический квадрат — он заполнен целыми числами от 1 до n2. Причём в судоку введено ещё одно правило — цифры не должны повторяться во внутренних квадратах со стороной 3 клетки. Совпадение сумм по главным диагоналям в судоку не проверяется.
Сумма чисел в каждой строке, столбце и на диагоналях нормального магического квадрата, называется магической константой. Магическая константа нормального магического квадрата зависит только от n. Например, для квадрата со стороной 3 клетки она равна 15.
Многие почитатели головоломки судоку искренне считают её восточным изобретением. В чём-то они правы. Первый известный нормальный магический квадрат третьего порядка, созданный человечеством, датируется 2200 годом до н.э. Он был изображён на панцире черепахи в Древнем Китае. В 13 веке китайский ученый Ян Хуэй и его последователи плотно занимались проблемой методов построения магических квадратов.
Древняя мудрость — магический квадрат на панцире черепахи
Самым ранним появлением магического квадрата в европейском искусстве считается квадрат 4 на 4, изображённый на гравюре Альбрехта Дюрера «Меланхолия». Ссылки на эту гравюру до наших дней путешествуют по страницам приключенческих таинственных романов. Вообще, с самых древних времён магическим квадратам приписываются мистические свойства (о чём красноречиво говорит их название). Известны, например, древние магические квадраты, в которых с магической константой совпадают также суммы чисел по ломаным диагоналям (диагонали, которые образуются при сворачивании квадрата в тор) в обоих направлениях. Самый ранний квадрат четвёртого порядка обнаружен в надписи 11 века в индийском городе Кхаджурахо.
Альбрехт Дюрер, «Меланхолия»
Проблема составления магических квадратов такая же древняя, как и сами эти квадраты. Математики разных эпох бились над этой задачей, но в общем математическом смысле она так и осталась неразрешённой: общий метод построения всех магических квадратов неизвестен.
Сложное в простом
Многие сравнивают судоку с шахматами. На это есть много причин. Магические квадраты, прародители судоку, как и шахматы, появились в глубокой древности. За кажущейся простотой правил (у судоку они даже гораздо проще, чем у шахмат) скрывается огромное число комбинаций. Например, количество возможных комбинаций в судоку 9 на 9 составляет 6 670 903 752 021 072 936 960. Кстати, это всего 0,00012% от общего числа латинских квадратов со стороной 9 клеток. Правда, справедливости ради, стоит заметить, что число по-настоящему уникальных комбинаций (без поворотов и зеркальных отражений) составляет 5 472 730 538. Это число выглядит скромнее, однако и оно производит впечатление.
Обе игры — судоку и шахматы — с самых древних времён имели особый сакральный смысл и нередко их пути пересекаются. Связь магических квадратов и шахмат более чем наглядно показал Леонард Эйлер. В 18 веке он попытался получить полный магический квадрат непрерывным обходом этого квадрата ходом коня (узнаёте распространённую шахматную задачу?). В итоге окончательно сделать это ему не удалось: в главных диагоналях суммы чисел отличались от магической константы. Более мягкий вариант магического квадрата — совпадение сумм по диагоналям не обязательно — Эйлер назвал «латинским квадратом». При решении этой задачи он пользовался латинскими буквами вместо чисел. Судоку, собственно, и является таким латинским квадратом. Существует понятие «обобщённого» судоку на поле произвольного размера N2 на N2, разделённого на меньшие квадраты со стороной N клеток. Всего на таком поле N4 клеток, в некоторых из которых уже стоят числа от 1 до N2. В итоге задача по заполнению такого поля числами и есть задача по решению судоку в более общем виде.
Настольный набор для решения судоку
Зоопарк
Любая популярная игра или головоломка рано или поздно обрастает целым зоопарком вариаций, клонов и модификаций. Так, например, было и с кубиком-рубика, и с тетрисом. Не избежало такой участи и судоку. Классическим считается вариант 9 на 9 клеток. Существуют варианты квадратов со сторонами 16 и даже 25 клеток. Эти гиганты предназначены для опытных игроков и требуют для своего разгадывания воистину титанических усилий.
Гигантское судоку с буквами
Варьируются не только размеры квадратов, но и сами правила головоломки. Например, существуют судоку, в которых всё поле изначально пустое: в нём нет цифр, проставленных автором, однако есть другая информация. Всё поле разбивается на прямоугольники различных формы и размера, причём у каждого прямоугольника указывается сумма входящих в него цифр.
Есть специальные детские судоку, состоящие всего из четырёх клеток. Существуют судоку, основанные не на латинских квадратах Эйлера, а на более общих магических квадратах. В таких головоломках общий квадрат не делится на маленькие квадратики, но введено дополнительное условие: требуется, чтобы не только в каждой строке и в каждом столбце, но и на двух главных диагоналях каждая цифра встречалась только один раз.
В детстве у многих была головоломка, основанная на кубике-рубика, но с гранями треугольной формы. Не избежало «треугольности» и судоку. Есть варианты, где необходимо заполнить треугольные клетки цифрами от 1 до 9. Всего треугольников шесть, они соприкасаются друг с другом двумя ячейками каждый и вместе образуют что-то вроде цветка. Необходимо, чтобы в каждом из шести больших треугольников и каждой линии по всем трём направлениям все цифры были разными.
Треугольное судоку типа «Хоши»
Любители изобретают на основе судоку множество задач с дополнительными условиями.
Культурное явление
Учитывая популярность судоку, нет ничего удивительного в том, что по всему миру существуют многочисленные клубы и сообщества любителей этой игры. Первый мировой чемпионат по судоку был проведен в Италии в марте 2006 года. Второй — в марте 2007 года, в Праге. С 2006 года под эгидой клуба «Диоген» (это не тот, в котором все молчат, а тот, в котором разгадывают головоломки) проводится чемпионат по судоку в России.
На одном немецком сайте проводится бесконечное интернациональное состязание среди поклонников судоку. За каждую разгаданную головоломку зарегистрированному пользователю начисляются очки. Алгоритм расчёта очков прост, как и правила головоломки. Количество разгаданных клеток отнимается от общего количества клеток, затем умножается на коэффициент сложности головоломки (от 1 до 3). Затем вычитаются баллы за подсказки (3, 6 или 9 баллов в зависимости от сложности). Отрицательные значения гуманно обнуляются. Вместо того, чтобы просто с карандашиком разгадывать головоломки на бумажке или задумчиво тыкать в экран телефона, подбирая числа, каждый может потешить своё самолюбие и сразиться с любителями судоку по всему миру. Кстати, очки суммируются не только в мировом масштабе, но и по странам, регионами и городам. Применение различных автоматических решателей запрещено кодексом сайта и игровое сообщество сайта зорко следит за тем, чтобы всё было по-честному.
Написание программы для автоматической генерации задач судоку любой сложности доступно любому программисту: алгоритмы известны, правила игры просты, для отображения полученного варианта достаточно даже текстового интерфейса. Поэтому в сети существует несметное множество онлайновых и офлайновых генераторов квадратов: каждый может выбрать на свой вкус. Большинство программ не только генерируют задачи, но и предоставляют удобный интерфейс для их решения. Практически все судоку, публикуемые в прессе, составлены с помощью таких программ. Выпускаются даже простенькие электронные игры судоку с чёрно-белым жидкокристаллическим экранчиком.
Электронный вариант игры
Однако в мире судоку есть свои эстеты. Настоящие знатоки игры ценят судоку, составленные вручную! Такое явление сложно объяснить — его надо почувствовать, самому погрузившись в решение судоку. Это немного похоже на шахматные этюды: мало просто придумать комбинацию на доске и поставить задачу, необходимо ещё, чтобы эта комбинация имела изящное решение. В судоку, как и в шахматах, скрыта своя необычная красота. Один и тот же иероглиф можно написать по-разному, из одного и того же квадрата, полностью заполненного числами можно сделать сотни разных задач, оставляя те или иные числа в качестве исходных.
Магнитная доска для игры в судоку
Судоку сегодня — это огромная индустрия: клубы и сообщества, сайты, телевизионные шоу, программы для генерации задач и их решения, книги с задачами и учебники по стратегиям решений, многочисленные настольные варианты игры. Бумага и карандаш, простейшие правила и целое море удовольствия!
Статья была впервые опубликована в журнале «Компьютерра» в 2010 году.
