Pull to refresh
114
36
Артём Рипатти @ripatti

Математик-программист

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

upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.
AlphaGo натравливали играть против своих копий, тоже в некотором смысле обучение из взаимодействия. Вместо эмоций — оптимизация целевой функции.
Автор же написал, что гуманитарий. Так и должно быть.

Information

Rating
382-nd
Location
Уфа, Башкортостан(Башкирия), Россия
Registered
Activity