Любителям судоку: найден простой алгоритм решения
24 марта 2009, 10:02 [ «Аргументы Недели» ]
Почетный профессор университета Уинтропа в Южной Каролине Джеймс Крук опубликовал в журнале Notices of the AMS («Заметки Американского математического общества») статью «A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles», излагающую простой способ решения головоломки судоку на любом уровне сложности. Об этом сообщает Лента.ру.
Для решения судоку по новому методу не требуется вычислительной техники, достаточно ручки и бумаги. Алгоритм Крука — первое математическое описание способа решения популярной головоломки. Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.
Недостатком представленного алгоритма является его трудоемкость. В каждую пустую клетку следует вписать недостающие цифры и начать перебор. Решение головоломки круковским способом занимает около часа. Обычно ее решают за 20 минут.
Математики заинтересовались судоку несколько лет назад. Одной из работ, на которые опирался Джеймс Крук в своем исследовании, была «Sudoku Squares and Chromatic Polynomials», авторы которой применили метод раскраски карты из теории графов для решения судоку.
