Судоку – это, возможно, одна из самых наших любимых головоломок, но это не просто способ убить несколько свободных секунд (или часов). Затягивающая числовая головоломка также содержит в себе некоторые интересные математические крупицы.

Судоку состоит из сетки 9 × 9, один квадрат состоит из меньшей сетки 3 × 3. В каждом квадрате игрок должен заполнить клетки цифрами от 1 до 9 так, что каждое число появляется только один раз в ряду и колонке всего большого квадрата. Кроме того, каждое число должно появляться один раз в каждом квадрате 3 × 3. Создатель головоломки раскидывает несколько цифр в квадрате, они являются подсказками, которые помогают игроку решить задачу. Еще одной особенностью судоку является то, что у каждой головоломки есть только одно решение.

Группа математиков во главе с Гэри МакГуайром из Дублинского университетского колледжа обнаружила, что минимальное количество подсказок, нужное для уникального – то есть единственного – решения, равно 17. Если в головоломке меньше подсказок, то у нее не может быть уникального решения. Однако МакГуайр и его команда не смогли найти этому доказательства. Вместо этого они использовали грубую вычислительную мощность для поиска по всем возможным сеткам судоку. На самом деле, они потратили 7 миллионов часов вычислительного времени в Дублинском центре высокопроизводительных вычислений. Им была необходима вся компьютерная мощность, которую они могли использовать, так как число возможных раскладок судоку огромно: 6 670 903 752 021 072 936 960. Однако исследователям удалось уменьшить это число до более приемлемого размера с помощью алгоритма, основанного на принципе, что некоторые раскладки математически эквивалентны.

Все это показывает, что даже развлечение в вашей газете может содержать в себе интересную математику.

В 2002 году математики утвердили, что судоку является NP-полной задачей. (NP – недетерминированное полиномиальное время.) Что это значит? В сущности, не существует быстрого и легкого пути решения судоку, даже если очень легко определить, является ли данное решение правильным. NP время очень длительное. Что это значит для судоку? Что не существует быстрого и легкого пути решения судоку, даже если очень легко определить, является ли данное решение правильным.