[закопировано из моего тг-канала]
Решил тут попробовать новый эпистолярный жанр под названием полет мысли. Писать не просто про какие-то идеи, а про то как они возникают. Название канала обязывает. Кто знает, возможно жанр окажется востребованным, когда люди наконец поймут, что для построения сильного ИИ недостаточно моделей, экстраполирующих какие-то тупые датасеты. Чтобы научить машину думать, надо иметь достаточно примеров, как это делает человек. С этим беда, никто не концептуализирует и не коллекционирует когнитивные схемы.
Психологи, наверное, коллекционируют. Но кто ж о них, гуманитариях, вспомнит при разработке сильного ИИ.
--------------------------
Недавеча по долгу службы пытался понять, как работают SMT-солверы. Мне коллега посоветовал поковырять Z3 solver, оказалось действительно довольно здравой штукой. На сайте есть javascript-овые примеры. Довольно стремный синтаксис, зато можно прямо в браузере позапускать, ничего не устанавливая. Самый впечатляющий готовый пример - решалка судоку. Вполне бодро процентов 70-80 пустоты в заданном примере заполняет.
Я правда человек мнительный и жизнью потрепанный, чую везде обман, поэтому захотел засунуть туда какой-то свой пример начальной расстановки циферок. А то вдруг этот сайт выдает всегда один ответ посчитанный для конкретного примера. Ну или пример подобрали какой-то особо хороший, шоб летало.
Возник вопрос откуда взять примеры начальных конфигураций, которые в принципе решаются. Нормисы наверное полезли бы интернет, но мне как-то в голову не пришло. Разумеется, я первым делом запустил шарманку на абсолютно пустой доске. Такой подлости солвер не ожидал и выдал ошибку таймаута.
Почувствовал свое интеллектуальное превосходство над бездушной машиной, потому что ну уж хоть какой-то пример собранного судоку я могу придумать из соображений симметрии. Ну, типа, поставить в первую строчку от 1 до 9 по порядку, а остальных строчках циклически сдвигать расстановку на, соотв., 3,6,1,4,7,2,5,8.
Поудаляв две трети значений, засунул штуку в солвер. Солвер выдал правильное решение, но не такое как было у меня, хотя отдельными местами похожее. Тем самым проверку на вшивость прошел.
--------------------------
Я пожалел, что не знал о солверах, когда ставил эксперименты с числом Бухштабера. Маялся тогда, чтобы правильно перебор сделать, а в солверах это уже по сути решили универсальным образом.
Есть как минимум одна задача про число Бухштабера, в которых солвер не поможет. А именно решить, как правильно говорить: инвариант Бухштабера или число Бухштабера. Так и так пишут, нет стандарта.
С одной стороны, инвариант - это что-то помогающее различать объекты. А перед нами чересчур эзотеричная хрень, чтобы кто-то на полном серьезе его использовал для различения симплициальных комплексов. Его и считать-то вообще говоря неизвестно как. С другой стороны, как заметил папа перед моей защитой, у словосочетания "число Бухштабера" апокалиптическая коннотация:
"Здесь мудрость. Кто имеет ум, тот сочти число зверя, ибо число это человеческое; число его шестьсот шестьдесят шесть." Откр.13:18
Считать - это уже по части современных технологий. Поток работ китайских студентов про число Бухштабера, приходящих на рецензию, как-то подыссяк. Но, отвечаю, следующий, кого мне пришлют с 10 страницами занудного перебора, получит в рецензии ссылку на Z3. Казалось бы молодежь должна лучше в кнопки тыкать и быть в курсе хороших технологий. Но что-то пока такое редко наблюдается.
<старческое бурчание> Всему-то всех учить надо.</старческое бурчание>
--------------------------
Однако я остался с вопросом, насколько вообще может быть много свободы у собранных судоку. Есть ведь очевидные операции, которые переводят решение в решение - перестановки первых трех строчек, вторых трех строчек, третьих трех строчек, перестановки трехстрочных блоков, аналогично со столбцами, переименование цифр, симметрии квадрата. Много симметрий. Казалось бы с точностью до симметрий собранных судок (судоков?) должно быть не очень много.
Но тут я уже сообразил, что этот вопрос человечество наверняка разрешило, и оказался прав. Вот https://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Symmetry.html пишут, что собранных судок вообще 6670903752021072936960, а если с точностью до симметрий, то 5472730538. Дохера как ни крути. Вычисление не rocket science: компухтер + лемма Бернсайда. Норм студентам в качестве проекта, можно и умным школьникам, пусть Sage погрызут.
--------------------------
По ходу осознавания группы симметрий судоку понял, что вот эта самая подгруппа в группе перестановок (допустим строчек), которая переставляет внутри троек, или тройки блоками - это группа симметрий тернарного дерева (высоты два).
Если бы только циклически все сдвигала, то получилась бы силовская 3-подгруппа в S_9. Википедия пишет, что силовские p-подгруппы в S_{p^k} - они вот как раз такие, циклические сдвиги веток p-арных деревьев глубины k, ну то есть их действия на множестве листьев.
Это прикольно, я раньше не осознавал, что кружковые задачи в стиле "на сколько нулей оканчивается 2024! ?" дают некий инсайт о том, как выглядят силовские подгруппы в группе перестановок.
--------------------------
Возвращаясь к судоку, однако, возникла мысль, что раз уж у нас столько принципиально разных вариантов ответов - то, наверное, мы слишком малого требуем от судоку.
Ну так-то понятно, что в глубине души поле 9х9 - это на самом деле 4-мерный куб 3х3х3х3. Если обозначить его координаты за a,b,c,d, то классические правила говорят, что (1) любое множество вида (a,b)=(const,const) - строчка то бишь - не содержит повторов (2) любое множество вида (c,d)=(const,const) - столбец - не содержит повторов (3) любое множество вида (a,c)=(const,const) - квадратик - не содержит повторов. Тогда, казалось бы, почему бы не наложить аналогичные условия на оставшиеся три пары координат? Будем называть такие судоку грассмановыми.
В моем наивном циклическом примере помимо трех базовых условий выполнено еще, что любое множество (b,d)=(const,const) не содержит повторов. Но оно все-таки до грассманова не дотянула. Я решил придумать грассманово судоку.
Придумал на основании более хитрых циклических сдвигов...
--------------------------
Воть
|1 2 3|9 7 8|5 6 4|
|4 5 6|3 1 2|8 9 7|
|7 8 9|6 4 5|2 3 1|
—————————
|8 9 7|4 5 6|3 1 2|
|2 3 1|7 8 9|6 4 5|
|5 6 4|1 2 3|9 7 8|
—————————
|6 4 5|2 3 1|7 8 9|
|9 7 8|5 6 4|1 2 3|
|3 1 2|8 9 7|4 5 6|
Я не знаю, сколько бывает грассмановых судок с точностью до симметрий. Полагаю, что а. меньше чем обычных, б. все же больше одного.
--------------------------
Мне подумалось, что надо концептуализировать процесс построения грассманова судоку. Получилось красиво.
Посмотрим на поле грассманова судоку как на аффинное пространство V=GF(3)^4 - что может быть естественнее. Выберем в V двумерное векторное подпространство П, которое трансверсально каждой из 6 координатных 2-подпространств в V (то есть они пересекаются только в нуле). Если такое получится найти, то рассмотрим точную последовательность
П --> V --> V/П = GF(3)^2 = [9]
Вторая стрелка и будет искомой расстановкой циферок на поле грассманова судоку. Ну типа потому что прообраз каждой циферки - это аффинно сдвинутое ядро П, если П трансверсально пересекает координатные векторные подпространства, то и все его аффинные сдвиги трансверсально пересекают все аффинные сдвиги координатных плоскостей. Что и хотелось.
Осталось заметить, что плоскость П таки можно правильно подобрать. Например, можно взять плоскость порожденную векторами
(1,1,0,1) и (0,2,1,1) mod 3
Никакой ненулевой вектор этой плоскости не имеет двух нулевых координат. Победа.
И гипотеза, про которую вообще без понятия, верна она или нет. Правда ли, что любое грассманово судоку получается с помощью описанного аффинного финта ушами? Не уверен, что солверы смогут как-то разумно и гарантированно перебрать все грассмановы судоку. Хотя с другой стороны обычные судоки как-то же люди перебрали...
--------------------------
Такая себе мысль близка к кульминации.
Неожиданный факт. Над полем GF(2) не бывает грассманова судоку. И аффинного грассманова не бывает, и вообще никакого грассманова не бывает. Можно руками доказать.
Тот факт, что существует аффинное грассманово судоку над GF(3), но не существует над GF(2) - это утверждение о том, что mod 2 число Бухштабера (оно же вещественное число Бухштабера) полного графа на 4 вершинах меньше 2, а mod 3 число Бухштабера того же графа - равно 2.
Я знаю, на меня подписаны обобщенные бухштаберята, и они должны были смекнуть, куда все идет, еще когда появилась точная последовательность дискретных торов несколько абзацев тому назад. Ее такую красивую всегда рисуют, когда про характеристические функции пишут.
Кто понел - айда статью запилим. Пока китайцы и сербы не понабежали. Связь с судоку - это лучшее, что случалось с числом Бухштабера за последние 10 лет, я гарантирую это.
Комментариев нет:
Отправить комментарий