Почетный профессор университета Уинтропа в Южной Каролине (США) Джеймс Крук опубликовал в журнале "Заметки Американского математического общества" статью, излагающую простой способ решения головоломки судоку на любом уровне сложности.
Для решения судоку по новому методу не требуется вычислительной техники, достаточно ручки и бумаги. Алгоритм Крука - первое математическое описание способа решения популярной головоломки. Он состоит в обходе вершин дерева решений до тех пор, пока не найдено верное.
Недостатком представленного алгоритма является его трудоемкость. В каждую пустую клетку следует вписать недостающие цифры и начать перебор. Решение головоломки круковским способом занимает около часа. Обычно ее решают за 20 минут.
Математики заинтересовались судоку несколько лет назад. Одной из работ, на которые опирался Джеймс Крук в своем исследовании, была "Sudoku Squares and Chromatic Polynomials", авторы которой применили метод раскраски карты из теории графов для решения судоку.
По материалу Лента.Ру
Судоку - основанная на логике головоломка-пазл с числами. В переводе из японского языка "су" помечает слово "число", "доку" имеет множество разных переводов, но в целом означает что-то одно, единичное, целостное. Оригинальное название головоломки японской очень трудно выговорить, и для англичан его пришлось сократить к "Sudoku".
Решение головоломки не требует математических расчетов, но требует терпения и способности к логическому мышлению. По некоторым данным решения головоломок Судоку улучшает память, мышление, а также препятствует развитию и даже лечит заболевание связанные с головным мозгом (таких, как болезнь Альцгеймера).
Игровое поле состоит из квадрата, размером 9х9, разделенного на меньшие квадраты (их еще называют "регионы") со стороной 3х3 клеточки. Таким образом, все поле насчитывает 81 клеточку. В некоторых из них уже в начале игры расположены числа (от 1 до 9). В зависимости от того, сколько клеточек уже заполнено, конкретную судоку можно отнести к легким или сложным.
Цель головоломки - необходимо заполнить свободные клеточки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3х3, каждая цифра встречалась лишь один раз. Правильная головоломка имеет лишь одно решение.
Математическая основа
Количество возможных комбинаций в судоку 9х9 составляет за расчетами Бертхама Фельгенхауэра (англ. BertramFelgenhauer) 6 670 903 752 021 072 936 960.
4 
1
Комментарии