Проверяемый контрпример: одна сетка и два корректных завершения

Обложка собрана кодом из поля, которое используется в тесте. Четыре пропуска допускают два завершения.

Главная ошибка наивного генератора судоку — проверять, что решение существует, но не проверять, что оно единственное.

Вот почти заполненное поле:

534..8912
672195348
198342567
859..1423
426853791
713924856
961537284
287419635
345286179

solve() быстро заполнит четыре пропуска. Только завершений здесь два: цифры 6 и 7 можно переставить, не нарушив ни строку, ни столбец, ни блок.

Одна сетка может иметь два корректных решения

countSolutions(puzzle, 2) останавливается после второго решения и возвращает 2.

Это не демонстрационная картинка. Та же строка из 81 символа лежит в solver.spec.ts, тест так и называется: «контрпример из лида действительно имеет два решения».

Я реализовал три стратегии поиска, а MRV и propagation дополнительно сравнил на наборах задач. Ещё измерил две операции: получение первого решения и доказательство того, что второго решения нет. Вторая вызывается после каждой попытки убрать подсказку, поэтому она в основном определяет цену генерации. React, Web Worker и тесты появятся дальше как обвязка этого поиска, а не как отдельные темы.

Это первый выпуск рубрики «ИграКОД» — про алгоритмы через запускаемые мини-игры. Ранее в цикле выходили материалы про useEffect, any, перенос TypeScript на Go, варианты архитектуры React-магазина и мы собирали и разбирали комбайн.

Перед кодом договоримся о трёх метриках. nodes — присваивания-догадки, из которых поиск может откатиться. deductions — форсированные ходы: голые и скрытые одиночки. Здесь и далее под deductions я считаю только эти две реализованные техники. Время замеряется пакетами по 20 вызовов, чтобы субмиллисекундные операции меньше зависели от шума таймера; для каждого поля берётся медиана пяти серий. Этот протокол используется для сравнения решателей. Генерация измеряется отдельно, поскольку один её запуск значительно дороже.

У генератора есть ещё два счётчика: сколько полных сеток он успел попробовать и сколько раз вызвал countSolutions(..., 2). Они важны: финальное поле может решаться мгновенно, хотя по пути генератор отбросил десятки кандидатов.

Сам алгоритм генерации давно известен. Схему «полная сетка → удаление подсказки → подсчёт решений» разбирали на Хабре ещё в 2013 году. Здесь интересен измеряемый путь от решателя до генератора и неприятные контракты, которые обнаружились по дороге.

Поле в коде — Uint8Array на 81 значение. Геометрия строк, столбцов и блоков вычисляется один раз. У клетки двадцать уникальных соседей. Множество кандидатов хранится в девятибитной маске, поэтому локальная проверка хода дёшева. Игровой интерфейс принимает конфликтующую цифру и подсвечивает её, а решатель перед поиском проверяет целостность всей сетки.

Первый решатель берёт очередную пустую клетку и перебирает допустимые цифры:

function search(work: Grid, from: number): boolean {
    let cell = from;
    while (cell < CELLS && work[cell] !== 0) cell++;
    if (cell === CELLS) return true;

    for (const digit of candidates(work, cell)) {
        counter.nodes++;
        work[cell] = digit;
        if (search(work, cell + 1)) return true;
        work[cell] = 0;
    }
    return false;
}

На трудном примере Питера Норвига такой порядок посещает 9 727 396 узлов. Большая часть работы уходит на широкие ветки, выбранные слишком рано.

Minimum remaining values выбирает клетку с минимальным числом кандидатов:

function selectMrvCell(work: Grid): number {
    let best = -1;
    let bestCount = SIZE + 1;

    for (let cell = 0; cell < CELLS; cell++) {
        if (work[cell] !== 0) continue;
        const count = countDigits(candidatesMask(work, cell));
        if (count < bestCount) {
            best = cell;
            bestCount = count;
            if (count <= 1) break;
        }
    }
    return best;
}

Рекурсия осталась той же, но на примере Питера Норвига счётчик падает до 718 узлов.

Третий решатель перед догадкой исчерпывает голые и скрытые одиночки. Такие ходы сразу попадают в deductions:

function search(work: Grid): boolean {
    const filled: number[] = [];
    if (propagateSingles(work, filled, counter) === "contradiction") {
        undoFills(work, filled);
        return false;
    }

    const cell = selectMrvCell(work);
    if (cell === -1) return true;

    for (const digit of candidates(work, cell)) {
        counter.nodes++;
        // догадка, рекурсивный спуск, откат
    }
}

На том же поле остаётся 25 узлов. Задачи уровня easy из сгенерированного набора проходят вообще без догадок.

Первая таблица показывает поведение реализаций внутри принятой модели сложности. Она не проверяет рейтинг независимо: уровень поля сам определяется числом ветвлений решателя с propagation.

MRV и propagation: узлы перебора по уровням

Среднее по 12 полям каждого уровня; вертикальная шкала логарифмическая.

Когда я впервые увидел соседние строки easy и evil, решил, что перепутал подписи: последовательный перебор потратил на поле easy при seed = 1 целых 8,4 млн узлов, а на evil — всего 5 718. Перезапустил набор, получил те же числа. Классификатор здесь ни при чём: порядок клеток у примитивного алгоритма просто очень неудачен для первого поля.

Чтобы не замыкать сравнение на собственном генераторе, я прогнал все 95 задач из публичного набора top95 Питера Норвига. Они не проходят через наши уровни. В таблице приведены средние по всему набору; максимум относится к решателю с propagation:

Все 95 полей имеют единственное решение. На этом наборе распространение ограничений тоже срезает поиск, хотя цифры уже ничего не говорят о шкале easy/evil.

Если коротко: MRV сокращает число неудачных веток, а propagation позволяет вообще не открывать часть этих веток.

Генерация начинается с полной случайной сетки. Затем клетки перемешиваются и удаляются по одной или центрально-симметричными парами. Каждый кандидат проходит проверку с лимитом два:

export function countSolutions(grid: Grid, limit = 2): CountResult {
    const search = (): boolean => {
        const filled: number[] = [];
        if (propagateSingles(work, filled, counter) === "contradiction") {
            undoFills(work, filled);
            return false;
        }
        const cell = selectMrvCell(work);

        if (cell === -1) {
            count++;
            undoFills(work, filled);
            return count >= limit;
        }
        for (const digit of candidates(work, cell)) {
            counter.nodes++;
            work[cell] = digit;
            const stop = search();
            work[cell] = 0;
            if (stop) {
                undoFills(work, filled);
                return true;
            }
        }
        undoFills(work, filled);
        return false;
    };

    search();
    return { count, nodes: counter.nodes, deductions: counter.deductions };
}

При count === 1 удаление принимается. Значение 2 означает, что найдено как минимум два решения, поэтому цифра возвращается. Ноль при корректной генерации невозможен: исходная полная сетка всё ещё остаётся допустимым решением. В коде такой результат считается нарушением инварианта и сразу приводит к ошибке. Третье решение искать уже незачем.

У «цены единственности» теперь три счётчика. Средние значения получены на 12 полях каждого уровня:

Поиск одного решения и доказательство единственности

График показывает только ветвления; дедукции и отношение времени приведены в таблице.

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

Нулевая строка easy больше не выглядит как «работы нет»: решатели делают в среднем 56 форсированных ходов. По времени поиск второго решения почти ничего не добавляет — 1,02×. На hard приходится проверить 141 дедукцию вместо 83, а время вырастает в 1,49 раза.

Это цена одной проверки готового поля. Генератор платит её после каждого кандидата на удаление и иногда начинает заново с другой полной сетки:

Здесь время включает всю генерацию. Один прогрев выполняется без таймера, затем берётся по одному замеру для 12 разных значений seed. В таблице приведены медианы этих 12 значений. Абсолютные миллисекунды на другой машине изменятся; счётчики работы останутся теми же.

Для seed = 7 я сначала решил, что сломан оценщик сложности. В интерфейсе была нажата кнопка evil, а под готовым полем появлялось hard. Оказалось, оба слоя показывали правду о разных вещах.

Генератор перебирал 40 вариантов, не находил уровень evil и возвращал ближайший hard. Компонент продолжал показывать запрос пользователя. Ошибка была в API: режим наилучшего приближения никак не отражался в типе результата.

Теперь контракт жёсткий. Генератор делает до 120 детерминированных попыток, возвращает точное совпадение или выбрасывает ошибку:

for (let attempt = 0; attempt < attempts; attempt++) {
    const result = digOnce(/* детерминированный sub-seed */);
    addAttempt(generation, result.stats);
    const rating = rate(result.puzzle);

    if (rating.level === level) {
        return { puzzle: result.puzzle, solution, rating, generation };
    }
}

throw new Error(`Не удалось сгенерировать уровень ${level} за ${attempts} попыток`);

Значения seed = 7 и seed = 8 закреплены регрессионными тестами. Для seed = 7 точный evil нашёлся на 95-й попытке:

Генератор для seed = 7: точный уровень evil и полная статистика попыток

95 попыток, 7 695 проверок уникальности, 16 445 узлов и 332 647 дедукций внутри этих проверок.

Уровни easy, medium, hard и evil — пороги по searchNodes эталонного решателя. Это удобно для воспроизводимого генератора, но не моделирует человека. Отдельный оценщик пробует одиночки, замкнутые кандидаты и голую пару — в смысле классических техник решения, описанных в HoDoKu. Его hardestTechnique иногда расходится с уровнем поиска.

Число подсказок тоже не спасает. McGuire, Tugemann и Civario доказали нижнюю границу в 17 подсказок для классического судоку с единственным решением. Граница говорит о существовании поля, а не о том, насколько трудно его решать.

Число подсказок против стоимости перебора

48 сгенерированных полей: Spearman = −0,191; Pearson для log10(nodes + 1) = −0,180.

В этой небольшой выборке монотонной связи не видно. Делать из 48 синтетических задач общий вывод о судоку я бы не стал. Для человеческой сложности нужен более богатый набор техник и данные реальных решателей — именно эту проблему подробно разбирает Radek Pelánek.

Граница между React UI, Web Worker и алгоритмическими модулями

React хранит сессию; решатель и генератор остаются обычными TypeScript-модулями.

React держит введённые цифры, карандашные пометки, выделение, таймер и историю undo/redo. Видимое поле вычисляется из исходных подсказок и пользовательского ввода. Правила компонентов не касаются: проверку конфликтов и завершения они вызывают из engine/.

Генерация уровня evil при seed = 7 занимает заметные секунды в браузере, поэтому поиск выполняется в Web Worker. Запрос получает id, а компонент применяет только последний ответ. Ошибка и таймаут завершают Promise; старый результат не может заменить более новый.

С трассой обнаружилась другая, очень визуальная ошибка. Финальное решение было правильным, но после отката на слайдере оставались одиночки из уже отвергнутой ветки. Теперь трасса ведётся как стек: при backtrack дедукции снимаются в обратном порядке. Тест проигрывает каждый шаг и сверяет промежуточное поле.

Главный инвариант генератора запускается на тридцати значениях seed:

it("каждое сгенерированное поле имеет ровно одно решение", () => {
    for (let seed = 1; seed <= 30; seed++) {
        const { puzzle } = generate({ seed });
        expect(hasUniqueSolution(puzzle)).toBe(true);
    }
});

В 56 тестах также проверяются три решателя, поле из лида, стек трассы, точные уровни для seed = 7 и seed = 8, таймер после undo, доступность доски, ошибки Web Worker и нулевой результат проверки уникальности. pnpm report заново создаёт JSON с измерениями и все графики.

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

Открыть стенд · посмотреть исходники

• Peter Norvig — Solving Every Sudoku Puzzle и его набор top95

• Donald Knuth — Dancing Links

• McGuire, Tugemann, Civario — There Is No 16-Clue Sudoku

• Radek Pelánek — Difficulty Rating of Sudoku Puzzles

• HoDoKu — Human Style Solving Techniques for Sudoku

• статьи Хабра про генерацию судоку и Algorithm X

Меня зовут Виктор Горбачёв. Больше семи лет пишу коммерческий фронтенд, последние два с лишним года — тимлид кросс-функциональной команды; преподавал React и TypeScript. В «ИграКОД» я разбираю алгоритмы через небольшие работающие проекты, которые можно запустить и проверить.

Подписывайтесь, чтобы не пропустить интересное. Лайки помогают понять, что статьи нужны и мне продолжать писать.