Кто изобрел судоку?
Дух судоку можно найти в головоломке, выросшей из математического увлечения магическими квадратами. Возьмите фигурные карты (валетов, дам, королей и тузов) из стандартной колоды карт и расположите их на сетке 4 × 4 так, чтобы ни в одном ряду и ни в одном столбце не было карт одной и той же масти или достоинства. Эту задачу впервые предложил в 1694 г. французский математик Жак Озанам, поэтому его можно было бы считать изобретателем судоку.
Математиком, несомненно заразившимся этой задачей, был Леонард Эйлер. В 1779 г., за несколько лет до смерти, Эйлер предложил другой вариант задачи. Пусть имеется шесть полков, униформа которых разного цвета, например красная, синяя, желтая, зеленая, оранжевая и фиолетовая. В каждом из полков имеется шесть военнослужащих различного звания, скажем полковник, майор, капитан, лейтенант, капрал и рядовой. Задача состоит в расположении военных на сетке 6 × 6 так, чтобы ни в одной шеренге и ни в одной колонне не было военных одинакового звания или цвета униформы. Эйлер задал этот вопрос для сетки 6 × 6, поскольку считал, что невозможно удовлетворительно расположить 36 военных. Лишь в 1901 г. французский математик-любитель Гастон Тарри доказал, что Эйлер был прав.
Эйлер также полагал, что эту головоломку невозможно решить для сетки размером 10 × 10, 14 × 14, 18 × 18 и т. д., если каждый раз прибавлять 4. Но это оказалось неверно. В 1960 г. три математика с помощью компьютера показали, что удается разместить военных 10 разных званий из 10 полков на сетке размером 10 × 10 вопреки убеждению Эйлера. Они не остановились на достигнутом и полностью опровергли гипотезу Эйлера, доказав, что сетка размером 6 × 6 представляет единственный случай, когда такое расположение невозможно.
Если вы хотите испытать себя в решении головоломки Эйлера на сетке 5 × 5, то загрузите соответствующий файл с веб-сайта «Тайн 4исел», вырежьте военных пяти званий из пяти полков. Проверьте, сумеете ли вы разместить их на сетке 5 × 5, чтобы ни в одной шеренге и ни в одной колонне не было военных из одного полка или одного звания. Эти магические квадраты иногда называют греко-латинскими квадратами. Возьмите первые n букв из латинского и греческого алфавитов и составьте все n × n возможных пар из латинских и греческих букв. Теперь расположите эти пары на сетке n × n, чтобы ни в одной строке и ни в одном столбце не было одинаковых латинских или греческих букв.
Жизнь в квадрате
Французский писатель Жорж Перек использовал греко-латинский квадрат размером 10 × 10 для придания структуры своему роману «Жизнь, способ употребления», изданному в 1978 г. В книге 99 глав, каждая из них соответствует комнате в парижском многоквартирном доме в десять этажей, на каждом из которых по десять комнат (комната под номером 66 не посещается). Каждая из комнат соответствует позиции в греко-латинском квадрате 10 × 10. Но при этом Перек использует не 10 греческих и 10 латинских букв, а, скажем, 20 авторов, разделенных на два списка по 10 человек. Когда он писал главу про какую-то комнату, то следил за тем, какие авторы приписаны ей, чтобы в ходе повествования использовать отрывки из их произведений. Например, в главе 50 греко-латинский квадрат Перека предписывает ему цитировать Гюстава Флобера и Итало Кальвино. Но в схему вовлечены не только писатели. В общей сложности Перек использует 21 различный греко-латинский квадрат, каждый из них наполняется благодаря двум спискам по 10 пунктов. Эти списки варьируются от мебели, художественного стиля и периода в истории до положений тел, принимаемых обитателями комнат.
Судоку несколько отличается от головоломки Эйлера о военных. В его классической форме вам необходимо разместить девять наборов чисел от 1 до 9 на сетке 9 × 9 так, чтобы ни в одной строке, столбце или квадранте 3 × 3 никакое число не встречалось два раза. Несколько чисел уже нанесены на сетку, и требуется заполнить пустые места. Не верьте тем, кто заявляет, что для решения этих головоломок не требуется математика. Они имеют в виду, что не требуется совершать арифметических действий – судоку, по существу, является логической задачей. Но тот же вид логического рассуждения, которое приводит вас к заключению, что в нижнем правом углу может быть только 3, встречается повсюду и в математике.
С судоку связаны несколько интересных математических вопросов. Один из них: сколькими различными способами можно расположить числа на сетке 9 × 9, чтобы удовлетворить правилам судоку? (Опять-таки под различными мы имеем в виду «существенно» различные: мы считаем два расположения одинаковыми, если одно из них переходит в другое вследствие простой симметрии, например перестановки строк.) Ответ был найден в 2006 г. Эдом Расселом и Фрэзером Джарвисом: 5 472 730 538. Этого вполне достаточно, чтобы газеты продолжали выходить еще какое-то время.
Однако другая математическая задача, связанная с этими головоломками, не была решена полностью. Какое минимальное количество чисел должно быть вначале нанесено на сетку, чтобы судоку решалось только одним способом? Понятно, что если этих чисел будет мало – скажем, 3, то головоломку можно будет решить многими способами, имеющейся вначале информации будет недостаточно для однозначного решения. Считается, что необходимо по крайней мере 17 чисел, чтобы судоку решалось только одним способом. Этот вопрос выходит за рамки головоломок, решаемых на досуге. У математики, лежащей в основе судоку, имеются важные следствия для кодов с коррекцией ошибок, с которыми мы познакомимся в следующей главе.
