В судоку часть клеток заполнена сразу — это подсказки, от которых отталкивается решающий. Чем их меньше, тем головоломка труднее. Долго никто не знал, где проходит нижняя граница: сколько цифр можно убрать, чтобы решение все еще оставалось единственным.
Мы разобрали, как этот вопрос закрыли, и увидели, что ответ дал не человек, а сплошной перебор на суперкомпьютере. История тут любопытнее самого числа, которое получилось в итоге.
Задача про минимум
Правильная судоку по определению имеет ровно одно решение. Если оставить слишком мало подсказок, решений становится несколько, и головоломка считается испорченной. Отсюда и вопрос: какое наименьшее число подсказок еще удерживает единственность ответа.
Примеры с семнадцатью подсказками находили давно и помногу — их собраны целые коллекции. А вот ни одной корректной сетки с шестнадцатью предъявить не смог никто. Из этого родилась гипотеза: меньше семнадцати не бывает. Доказать ее долго не удавалось, потому что проверять пришлось бы неподъемное число комбинаций.
Ответ дал перебор
В 2012 году группа из Университетского колледжа Дублина под началом Гэри Макгвайра вопрос закрыла. Обычный способ проверки не годился: вариантов слишком много даже для суперкомпьютера. Исследователи придумали более быстрый способ перебирать варианты и прогнали через него заполненные сетки, проверяя, не прячется ли где решение с шестнадцатью подсказками.
Не нашлось ни одного. Счет машинного времени шел на миллионы процессорных часов, а сама проверка заняла около года непрерывной работы. Так гипотеза стала фактом: минимум — семнадцать подсказок, ниже решение раздваивается. Отдельные примеры тут не помогают: нужно было пройти весь массив вариантов без единого пропуска.
Почему доказательство нельзя проверить глазами
Тут судоку попадает в один ряд с большой математикой. В 1976 году Кеннет Аппель и Вольфганг Хакен в Университете Иллинойса доказали теорему о четырех красках. Она говорит, что любую карту можно раскрасить четырьмя цветами так, чтобы соседние области отличались. Их доказательство тоже свелось к перебору огромного числа случаев машиной.
Эту теорему считают первой крупной, доказанной с помощью компьютера. Поначалу ее приняли не все: пройти такой перебор вручную человек не в силах, а значит, проверить работу привычным способом нельзя. Доверие пришло позже, когда расчет повторили и перепроверили независимо. С границей в семнадцать подсказок вышло ровно так же: число установила не теория, а полный машинный перебор.
Где проверить это самому
Увидеть разницу между трудной и легкой сеткой проще всего на практике. В Яндекс Играх предлагают судоку играть на готовых уровнях с разной сложностью, и число открытых подсказок как раз один из рычагов этой сложности.
Семнадцать — это не про то, как трудно решать, а про то, где кончается сама головоломка. Уберите еще одну цифру из такой сетки, и у нее появится второе решение. А значит, судоку перестанет быть судоку и превратится в задачу с несколькими ответами.

Комментировать