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

Почетный профессор университета Уинтропа в Южной Каролине Джеймс Крук опубликовал в журнале Notices of the AMS ("Заметки Американского математического общества") статью A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles, излагающую простой способ решения головоломки судоку на любом уровне сложности.

Как сообщает Lenta.ru со ссылкой на The Times, для решения судоку по новому методу не требуется вычислительной техники, достаточно ручки и бумаги. Алгоритм Крука - первое математическое описание способа решения популярной головоломки. Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.

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

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