Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

ИграКОД: Генератор судоку на TypeScript: почему найти решение проще, чем доказать единственность

01.08.2026 09:07:05 | Хабр
Хабы: Алгоритмы, TypeScript, JavaScript, Программирование, IT-стандарты

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

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

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-магазина и мы собирали и разбирали комбайн.

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro