23 марта 2009, 17:18

Открыт способ решения судоку любой сложности

Почетный профессор университета Уинтропа в Южной Каролине Джеймс Крук опубликовал в журнале Notices of the AMS статью, излагающую простой способ решения судоку на любом уровне сложности.
Для решения судоку по новому методу не требуется вычислительной техники, достаточно ручки и бумаги. Алгоритм Крука - первое математическое описание способа решения популярной головоломки, пишет The Times. Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.

Недостатком представленного алгоритма является его трудоемкость. В каждую пустую клетку следует вписать недостающие цифры и начать перебор. Решение головоломки круковским способом занимает около часа. Обычно ее решают за 20 минут.

Математики заинтересовались судоку несколько лет назад. Одной из работ, на которые опирался Джеймс Крук в своем исследовании, была "Sudoku Squares and Chromatic Polynomials", авторы которой применили метод раскраски карты из теории графов для решения судоку.
Чтобы получать лучшие материалы дня, недели, месяца, подписывайтесь на наш канал. Здесь мы добавляем смысла каждой новости.