А можно ссылку на пруф этого утверждения? А то мне известна только ссылка на доказательство оптимизированным брутфорсом (она есть в тексте перевода). И считали они там 7 миллионов ядролет (!) на кластере из 300 серверных машин (через MPI, а не BOINC). Причем программа была написана на ассемблере.
Давайте рассмотрим задачу попроще. Есть квадрат и мы красим его 4 угла в один из двух цветов — итого 16 вариантов. А сколько будет вариантов с учетом поворотов и отражений?
Там проблема в том, что некоторые решения при повороте на 90 градусов переходят друг в друга, а остальные — нет. Т.е. нам нужно все решения как-то разбить на 2 кучи и размер одной из них делить на 4, а размер другой — нет. А теперь представьте как их нужно разделять, если у нас есть кроме поворотов есть перемешивание строк, столбцов, и прочее (а также все их комбинации). И еще нужно понять какую кучу на что делить.
Верно, сначала мы сокращаем число полос 2612736 -> 36288 -> 416 -> 174 -> 71, а потом уже добиваем реальным перебором за 6 часов (вместо 6/71*36288, или сколько там было полос).
У разных решений можно дооткатываться до разного количества начальных задач. Впрочем, их можно разбить на классы, где в каждом классе одно и то же число различных задач (тогда можно откатываться только для одного решения из класса). Насчет этих вот классов — будет расписано во второй части перевода.
Проблема в том, что несколько задач могут иметь одно и то же решение. Например, если мы из полной сетки удалим одно из чисел (81 способом), то получим 81 задачу на одно решение, и все эти задачи будут различны.
Тут еще есть такой вопрос: какие полузаполненные сетки считать судоку — которые имеют ровно одно решение, или же просто подходят под Главное Правило. Второй вариант явно легче первого, а первый, вероятно, на сегодняшний день вообще не решаем.
Это уже вопрос терминологии. Можно считать что угодно, но написать «Под судоку мы будем понимать...». В статье авторы как судоку определяют начальную задачу, а конечную — как решение или полностью заполненную сетку. Каюсь, кое-где я заменяю одно другим, но из контекста ясно, о чем идет речь, просто мне в голову не приходило явно разделять эти понятия. Могу дополнительно все прописать более четко, если режет глаз.
Последнее число — это количество судоку без учета кучи симметрий вроде отражений, поворотов, перемешиваний троек строк/столбцов по блокам и тп. Т.е. количество действительно уникальных судоку.
Виноградов доказал не от 1 до N, а от N до бесконечности. Т.е. чтобы доказать тернарную гипотезу полностью, можно было бы просто проверить руками или на компьютере от 1 до N, если бы не астрономическое число N.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.
Правда, оказалось, там были чуть другие 6 символов.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.