IBM Research предложила октябрьскую задачу Ponder This: партия в Ultimate Tic-Tac-Toe ровно из 81 хода

Что предлагает задача

IBM Research держит серию головоломок Ponder This: в блоке связанных материалов к октябрьской задаче перечислены выпуски за май, июнь, июль и август 2026 года, а автором октябрьского выпуска указан Gadi Aleksandrowicz.

Октябрьская задача называется «The Ultimate Ultimate Tic-Tac-Toe Game» и посвящена не самой игре, а аккуратной конструкции: нужно предъявить партию, у которой одновременно выполняются три жёстких условия.

Правила Ultimate Tic-Tac-Toe

Игра идёт на доске 9 × 9, которая мысленно делится на девять малых досок 3 × 3; игроки обозначаются «X» и «O» и ходят по очереди, начиная с X.

Главное ограничение — переход хода: если игрок ставит символ в клетку (x, y), следующий игрок должен выбирать клетку в малой доске с координатами (x mod 3, y mod 3).

В качестве примера автор разбирает ход X в клетку (4, 6): это серединная правая малая доска, внутри неё — крайняя левая клетка среднего ряда, поэтому O обязан сыграть в средней левой доске (1, 0).

Как только в малой доске складывается выигрышная линия, доска считается «закрытой» и получает глобальное значение победителя; полностью заполненная доска без победителя тоже закрывается, но остаётся без глобального значения.

Если предписанная правилом малая доска уже закрыта, игрок волен выбрать любую клетку в любой незакрытой доске; сама игра выигрывается тогда, когда закрытые доски, рассматриваемые как клетки сетки 3 × 3, складываются в выигрышную линию.

Три условия «Ultimate Ultimate»

В обычной партии Ultimate Tic-Tac-Toe победитель определяется раньше, чем заполнится доска, — и именно это предлагается сломать.

По определению автора, «Ultimate Ultimate» партия обязана длиться 81 ход, то есть заполнить всю доску целиком.

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

Третье: победу приносит последний ход партии.

Автор отдельно оговаривает, что партия может содержать ходы, которые обычно сочли бы иррациональными: возможность закрыть малую доску разрешено игнорировать, потому что цель здесь — выполнить три условия, а X и O можно считать действующими заодно.

Как записывается решение

Клетки доски нумеруются числами от 0 до 80, начиная с левой верхней и далее по строкам: первая строка — это 0, 1,…, 8, вторая — 9, 10,…, 17 и так далее, поэтому партия записывается просто как последовательность чисел.

В качестве образца в тексте задачи приведена партия из 58 ходов, которая заканчивается победой O по диагонали из малых досок.

Доска в этом примере заполнена не полностью, поэтому он показывает запись партии и правило победы, но ответом на задачу не является: условие требует, чтобы партия длилась все 81 ход.

Цель задачи сформулирована прямо: найти «Ultimate Ultimate Tic-Tac-Toe» партию и оформить решение в описанном формате.

Почему условие жёсткое

Сложность в том, что все девять малых досок должны получить победителя ровно на последних девяти ходах: если хотя бы одна доска будет закрыта раньше, партия перестанет быть «Ultimate Ultimate», даже если доска в итоге заполнится целиком.

Отсюда же следует запрет на ничьи: полностью заполненная доска без победителя закрывается, но остаётся без глобального значения, а условие требует, чтобы каждый из последних девяти ходов закрывал доску именно победой.

Поэтому задача и не решается обычной игрой «на победу»: автор прямо разрешает ходы, которые в соревновательной партии сочли бы иррациональными, и предлагает рассматривать X и O как действующих заодно.

Бонусный вариант 5 × 5

За отдельную отметку «звёздочкой» предлагается решить ту же задачу для случая 5 × 5: 25 малых досок размером 5 × 5 клеток, а ходы в такой партии нумеруются от 0 до 624.

То есть базовый вариант требует собрать партию из 81 хода на девяти малых досках, а бонусный — из 625 ходов на двадцати пяти.

Как отправить ответ

Решения принимаются по адресу ponder@il.ibm.com: авторы обещают опубликовать имена тех, кто пришлёт правильное и оригинальное решение.

Там же оговорено право на анонимность — если публиковать имя не нужно, достаточно сказать об этом в самом письме, — и туда же можно присылать собственные идеи для будущих выпусков серии.