Каждая головоломка Griductive даёт смелое обещание: вам никогда не придётся угадывать. Каждую клетку можно определить исключительно с помощью логики, и у каждой головоломки есть ровно один правильный ответ.
Это не просто цель проектирования — это математическая гарантия, обеспеченная тем же классом решателей, который используется в исследовании операций и верификации микросхем. Этот пост объясняет, как это работает.
Почему единственность решения важна
Если у головоломки два допустимых решения, должна существовать хотя бы одна клетка, где и «Подозреваемый», и «Невиновный» удовлетворяют всем подсказкам. В этой клетке никакие рассуждения не помогут определить, какой ответ правильный — пришлось бы угадывать. Угадывание нарушает основной принцип дедуктивной головоломки.
Поэтому генератор не просто создаёт головоломки, которые случайно имеют одно решение. Он доказывает, что второго решения не существует, прежде чем головоломка будет опубликована.
Пятифазный конвейер
Каждая головоломка Griductive создаётся через пятифазный конвейер. Вот что происходит на каждом этапе.
Фаза 1: Генерация случайного решения
Генератор начинает с создания допустимой сетки-решения — случайного распределения «Подозреваемый» и «Невиновный» для каждой клетки. Это та истина, которую игрок в итоге должен будет вывести.
На данном этапе подсказок ещё не существует. Доска — просто случайная конфигурация, удовлетворяющая базовым структурным ограничениям (размеры сетки, количество подозреваемых в допустимом диапазоне).
Фаза 2: Формирование пула подсказок
Далее генератор исчерпывающе перечисляет все возможные подсказки, которые истинны на сетке-решении.
Griductive имеет более 26 различных типов подсказок — подсчёт, сравнение, пространственные, экзистенциальные, уникальности, связности и другие. Для каждого типа генератор проверяет каждую допустимую параметризацию на доске. Сетка 4x4 может породить тысячи подсказок-кандидатов. Сохраняются только подсказки, которые оказываются истинными на решении.
Это сырой материал, с которым работает генератор: огромный пул истинных утверждений, большинство из которых избыточны.
Фаза 3: Выбор минимального набора подсказок (самая сложная часть)
Здесь происходит основная работа. Генератору нужно выбрать небольшое подмножество подсказок из пула такое, что:
- Подсказки достаточны — вместе они сужают пространство решений ровно до одной допустимой доски.
- Ни одна подсказка не избыточна — удаление любой отдельной подсказки привело бы к появлению нескольких решений.
Генератор использует жадный подход с удовлетворением ограничений:
- Начать без выбранных подсказок. Пространство решений широко открыто — множество досок могут быть допустимыми.
- Оценить каждую подсказку-кандидат по тому, насколько она сужает пространство решений. Подсказка, исключающая 80% оставшихся вариантов, получает более высокую оценку, чем та, что исключает 10%.
- Выбрать подсказку с наивысшей оценкой и добавить её в набор.
- Повторно решить модель ограничений с обновлённым набором подсказок.
- Повторять, пока решатель не подтвердит, что осталось только одно решение.
- Сокращение: пройти по финальному набору и удалить любую подсказку, не являющуюся необходимой для единственности. Это делает головоломку чистой и не даёт игроку бесплатную информацию.
Результат — компактный и честный набор подсказок: достаточный для полного решения головоломки, без лишних подсказок.
Фаза 4: Оценка сложности
С зафиксированным набором подсказок генератор оценивает сложность головоломки по шкале от 0 до 100. Четыре фактора вносят вклад:
- Доля простых подсказок (35%) — Сколько подсказок являются прямыми подсчётами или утверждениями об идентичности. Больше простых подсказок — легче головоломка.
- Доля сложных подсказок (30%) — Сколько подсказок требуют многоступенчатого или пространственного рассуждения. Они требуют более глубоких цепочек дедукции.
- Дефицит информации (20%) — Насколько мало подсказок дано относительно размера сетки. Меньше подсказок — меньше данных для работы.
- Масштаб сетки (15%) — Более крупные сетки по своей природе сложнее для отслеживания. Головоломка 5x5 имеет почти втрое больше клеток, чем 3x3.
Каждый тип подсказки также имеет внутренний рейтинг сложности, основанный на требуемом рассуждении. Подсказка вроде «Джулия — подозреваемый» — примерно самая простая. Подсказка вроде «Джулия — единственный человек в ряду 3, у которого ровно 1 подозреваемый сосед» требует перекрёстной проверки нескольких клеток и оценивается значительно выше.
Фаза 5: Генерация подсказок-помощников и форматирование вывода
Наконец, генератор формирует последовательность подсказок-помощников — рекомендуемый порядок решения, который проводит застрявших игроков через головоломку по одному логическому шагу за раз. Подсказки упорядочены по глубине зависимостей: клетки, которые можно вывести сразу, идут первыми, а клетки, требующие длинных цепочек предыдущих выводов, — последними.
Финальная головоломка упаковывается со всеми данными, необходимыми игре: метаданные, набор подсказок, последовательность подсказок-помощников и оценка сложности.
Решатель: как доказывается единственность
В основе конвейера лежит Google OR-Tools CP-SAT — решатель на основе программирования в ограничениях, сочетающий распространение ограничений, целочисленное программирование и SAT-решение.
Как головоломка становится математической задачей
Каждая клетка на сетке моделируется как булева переменная: Подозреваемый (1) или Невиновный (0). Каждая подсказка превращается в одно или несколько математических ограничений на эти переменные.
Например:
- «В ряду 3 ровно 2 подозреваемых» становится:
cell[3,0] + cell[3,1] + cell[3,2] + cell[3,3] = 2 - «Все подозреваемые в столбце A связаны» становится: ограничение связности, гарантирующее, что клетки с подозреваемыми в столбце A образуют непрерывную цепочку без разрывов.
- «В ряду 1 больше подозреваемых, чем в столбце B» становится:
sum(row_1) > sum(col_B)
Как проверяется единственность
После сборки набора подсказок генератор задаёт CP-SAT точный вопрос: «При данных ограничениях существует ли более одного допустимого присвоения?»
CP-SAT не просто находит одно решение — он может перечислить все решения. Если решатель находит ровно одно, головоломка валидна. Если он находит два или более, генератор возвращается к Фазе 3 и добавляет ещё одну подсказку.
Это формальное доказательство, а не эвристика. CP-SAT исчерпывающе исследует всё пространство решений. Если он говорит, что решение одно, значит, оно ровно одно — точка.
Почему нельзя просто перебрать все варианты?
Сетка 5x5 имеет 25 клеток, каждая с 2 возможными значениями. Это 2^25 = 33 миллиона возможных досок. Полный перебор всех — медленный процесс, который не масштабируется.
CP-SAT работает значительно быстрее благодаря распространению ограничений: когда подсказка говорит «в ряду 3 ровно 2 подозреваемых», решатель немедленно сокращает пространство поиска для каждой клетки в ряду 3, не проверяя каждую комбинацию отдельно. Сложные подсказки усиливают этот эффект. На практике CP-SAT доказывает единственность для головоломки 5x5 за миллисекунды.
Что может пойти не так (и как мы это предотвращаем)
«Что если подсказка неоднозначна?»
Каждый тип подсказки имеет формальное математическое определение. «Соседи» всегда означают до 8 окружающих клеток, включая диагонали. «Связаны» всегда означает непрерывную цепочку смежных клеток. «Между» всегда означает клетки в одном ряду или столбце, исключая конечные точки.
Эти определения встроены непосредственно в модель ограничений — нет этапа интерпретации естественного языка, на котором могла бы возникнуть неоднозначность. Внутриигровой справочник Уточняющие детали показывает игрокам точное значение каждого пространственного термина.
«Что если в решателе есть ошибка?»
Решатель CP-SAT — это хорошо протестированный, широко используемый инструмент, поддерживаемый командой оптимизации Google. Но мы не полагаемся только на доверие. Каждая сгенерированная головоломка независимо проверяется:
- Автоматический решатель пытается решить каждую головоломку пошагово, моделируя действия игрока. Если он не может достичь полного решения исключительно через логическую дедукцию, головоломка отклоняется.
- Проверка корректности подсказок-помощников подтверждает, что каждая подсказка в последовательности логически обоснована — что указанная клетка действительно выводима из подсказок и ранее раскрытых клеток, а не из скрытой информации.
«Что если генерация подсказок пропустит граничные случаи?»
Каждый тип подсказки имеет формальную функцию оценки, протестированную на известных конфигурациях головоломок. Фаза генерации пула подсказок включает только подсказки, которые оказываются истинными на фактическом решении — подсказка, ложная на решении, никогда не может появиться в головоломке.
Результат
Когда вы открываете головоломку Griductive, вот что уже произошло:
- Было сгенерировано случайное решение.
- Тысячи подсказок-кандидатов были проверены на нём.
- Было выбрано минимальное, неизбыточное подмножество.
- Формальный решатель доказал, что ровно одно решение удовлетворяет этим подсказкам.
- Автоматический решатель независимо подтвердил, что головоломка решаема через чистую дедукцию.
- Была вычислена оценка сложности и сгенерирована последовательность подсказок-помощников.
Каждая головоломка, каждый день, для всех четырёх размеров сетки. Без исключений.
Обещание выполняется: если вы застряли, есть подсказка, которую вы ещё не использовали полностью. Если вам кажется, что возможны два ответа, перечитайте подсказки — логика всё разрешит. А если хотите доказательства, логический граф покажет вам точную цепочку дедукции от подсказок до решения.
Что дальше: подсказки, рассказывающие историю
Сейчас подсказки Griductive читаются как точные логические утверждения — ясные и однозначные, но, признаться, немного сухие. «В ряду 3 ровно 2 подозреваемых» справляется с задачей, но не заставляет почувствовать себя детективом на расследовании.
Мы активно работаем над тем, чтобы это изменить. Цель — разнообразить способы выражения подсказок, вплетая тематический колорит при сохранении той же логической точности. Представьте подсказки, привязанные к праздничным событиям, или оформленные как показания свидетелей с конкретного места преступления. Вместо стерильной формулы вы бы читали нечто, ощущающееся как настоящая улика из расследования.
Ключевое ограничение не изменилось: каждая подсказка должна оставаться непротиворечивой, однозначной и формально проверяемой. Решателю всё равно, звучит ли подсказка как учебник по математике или как нуарный детектив — его интересует только логическое содержание. Именно это разделение делает возможным более богатое выражение без ущерба для корректности.
Те же гарантии. Та же строгость. Но головоломки, которые ощущаются не как уравнения, а как дела, достойные раскрытия.
Никакого угадывания. Никакой удачи. Математически гарантировано.