ИграКОД: Генератор судоку на TypeScript: почему найти решение проще, чем доказать единственность
Главная ошибка наивного генератора судоку — проверять, что решение существует, но не проверять, что оно единственное.Вот почти заполненное поле: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-магазина и мы собирали и разбирали комбайн. Читать далее
03:45
03:24
15:50
