matematik
27-04-2009, 23:39
A Pencil-and-Paper, Algorithm for Solving Sudoku Puzzles, J. F. Crook
Почетный профессор университета Уинтропа в Южной Каролине Джеймс Крук опубликовал в журнале Notices of the AMS ("Заметки Американского математического общества") статью A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles, излагающую простой способ решения головоломки судоку на любом уровне сложности.
Для решения судоку по новому методу не требуется вычислительной техники, достаточно ручки и бумаги. Алгоритм Крука - первое математическое описание способа решения популярной головоломки. Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.
Недостатком представленного алгоритма является его трудоемкость. В каждую пустую клетку следует вписать недостающие цифры и начать перебор. Решение головоломки круковским способом занимает около часа. Обычно ее решают за 20 минут.
Математики заинтересовались судоку несколько лет назад. Одной из работ, на которые опирался Джеймс Крук в своем исследовании, была Sudoku Squares and Chromatic Polynomials, авторы которой применили метод раскраски карты из теории графов для решения судоку.
Хорошо, что хоть кен-кен сейчас есть. Это, вроде, еще лучше, чем судоку.
Кто-нибудь играл уже?
Почетный профессор университета Уинтропа в Южной Каролине Джеймс Крук опубликовал в журнале Notices of the AMS ("Заметки Американского математического общества") статью A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles, излагающую простой способ решения головоломки судоку на любом уровне сложности.
Для решения судоку по новому методу не требуется вычислительной техники, достаточно ручки и бумаги. Алгоритм Крука - первое математическое описание способа решения популярной головоломки. Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.
Недостатком представленного алгоритма является его трудоемкость. В каждую пустую клетку следует вписать недостающие цифры и начать перебор. Решение головоломки круковским способом занимает около часа. Обычно ее решают за 20 минут.
Математики заинтересовались судоку несколько лет назад. Одной из работ, на которые опирался Джеймс Крук в своем исследовании, была Sudoku Squares and Chromatic Polynomials, авторы которой применили метод раскраски карты из теории графов для решения судоку.
Хорошо, что хоть кен-кен сейчас есть. Это, вроде, еще лучше, чем судоку.
Кто-нибудь играл уже?