Компьютерра: Компьютерра PDA 20.02.2010-26.02.2010

Правила

Для тех, кто все же не в курсе что такое судоку, кратко опишу правила этой головоломки. Много места для этого не потребуется: правило у судоку всего одно. Дан квадрат 9 на 9 клеток, в часть клеток уже вписаны цифры от 1 до 9. Необходимо заполнить остальные клетки, соблюдая правило: в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра от 1 до 9 должна встречаться только один раз. Вот, собственно, и вся головоломка.

Сложность головоломки зависит от количества заранее расставленных цифр и их размещения. В мире судоку принято выделять четыре уровня сложности: простой, промежуточный, сложный и очень сложный ("diabolical" или "evil"). Простые головоломки решаются путем несложного сопоставления чисел. Судоку на промежуточном уровне может потребовать выполнения в уме некоторых расчетов. Сложный же уровень скорее всего потребует глубокого анализа и, как говорил наш преподаватель по высшей математике: "многочасового домашнего обдумывания".

История успеха

Официально датой рождения судоку в ее классическом виде считается май 1979 года. В этом году головоломка впервые была опубликована в журнале Dell Magazines под именем Number Place. Автором этой головоломки был американский архитектор из Индианы Говард Гарнс (Howard Garns). Первая головоломка "судоку" была нарисована Говардом на чертежной доске для собственного развлечения. Кстати, ему в это время уже было за 70. Как это часто бывает, при первой публикации имя автора где-то затерялось и головоломка вышла на страницах журнала анонимной. Имя Говарда указывалось только в общем списке авторов журнала, напечатанном мелким шрифтом, всякий раз, когда головоломка появлялась на страницах журнала.

Однако настоящую популярность головоломка обрела в 1984 году в Японии. Именно тогда она появилась на страницах японского журнала головоломок Nikoli. Тогда же появилось и само слово "судоку". Оно состоит из двух иероглифов: "су" и "доку", что в переводе с японского означает "числа рядом". Вообще, "судоку" - это сокращение от более длинного "Suuji wa dokushin ni kagiru" ("число может использоваться только один раз"). Интересно, что на сайте журнала по поводу истории головоломки написано только то, что она была позаимствована "в американском журнале головоломок".

2 ноября 2004 года головоломка впервые появилась на страницах культовой британской газеты "Таймс". А уж то, что появилось на страницах Таймс – становится известным всей Европе, а затем и всему миру. Головоломка судоку начала свое победное шествие по планете. Однако, ее истинный изобретатель не дожил до этого момента – он умер в ноябре 1989 года.

Моя жена, жившая в США как раз в этот период, рассказывала, что за короткое время судоку заполонили буквально всю Америку: их можно было увидеть в самолетах, автобусах, в офисах и в обычных домах. Судоку из New York Times вырезались, ксерокопировались, рассылались по почте (обычной, а не электронной). Ей самой знакомые неоднократно присылали ксероксы задачек из очередного номера. Америку охватила настоящая эпидемия судоку.

Магические предки

Иногда судоку по старой памяти (и не совсем правильно) называют "магическим квадратом". Однако, на это есть веские причины. Дело в том, что сам принцип заполнения квадрата числами по указанному правилу известен еще с глубокой древности. В общем математическом смысле это квадрат n на n клеток, заполненных числами (любыми, а не только от 1 до 9) таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях является одинаковой.

Головоломки, подобные судоку начали появляться в прессе еще в 19-ом веке. Например, в 1892 году во французской газете Le Sie`cle публиковались головоломки, основанные на магическом квадрате, которые в строгом смысле судоку не являлись.

В судоку реализован т. н. нормальный магический квадрат – он заполнен целыми числами от 1 до n 2. Причем, в судоку введено еще одно правило – цифры не должны повторяться во внутренних квадратах со стороной 3 клетки. Совпадение сумм по главным диагоналям в судоку не проверяется.

Сумма чисел в каждой строке, столбце и на диагоналях нормального магического квадрата, называется магической константой. Магическая константа нормального магического квадрата зависит только от n. Например, для квадрата со стороной 3 клетки она равна 15.

Многие почитатели головоломки судоку искренне считают ее восточным изобретением. В чем-то они правы. Первый известный нормальный магический квадрат третьего порядка, созданный человечеством, датируется 2200 г. до н.э. Он был изображен на панцире черепахи в Древнем Китае. В 13 веке китайский ученый Ян Хуэй и его последователи плотно занимались проблемой методов построения магических квадратов.