Еще раз о решении судоку

У нас на сайте уже есть статья о математических методах решения судоку, хочется продолжить цикл еще одной статьей (которая была опубликована в прошлом году) о необычном методе решения судоку.

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

судоку

 

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

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

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

 

Источник: Lenta.ru

 

комментарии (2)

bvz | 02.06.2016, 17:31
Ну и где способ-то? Дерево где? Решать перебором - это, извините, изобретение велосипеда.
Козладоев | 17.05.2012, 18:30
К сожалению, я - физик. Математический аппарат физики предлагает смотреть на задачу, как на 3-х этажный дом с тремя подъездами. Потому, что от латинского квадрата 9Х9 потребовали выполнять правило ещё и для девяти квадратов 3х3, возникает правило СЕГМЕНТА. Итак, строка, столбец, квадрат 3х3 и по три вертик. и горизонт. цифры (сегмент). Присмотритесь к любому ОТВЕТУ и сами сформулируйте правило сегмента. Любая из 90 цифр в 27 27 сегментах является либо членом "семьи" из трех цифр, либо входит в хоз. пару, либо является "гостем" и шляется по этим трем парам. И в подъездах и на этажах. Не было ещё ни одного расклада, который я не решил (не нашел ОТВЕТ) чисто ЛОГИЧЕСКИМ путём. С цепочкой ходов, каждый является следствием предыдущих. Без предположим и допустим. Можно употребить к одному из двух вариантов (без карандаша и резинки) конструкцию "если...то придётся... после чего ни фига не выйдет, поэтому применяем второй вариант. Как мог описал процесс нахождения ОТВЕТА ЛОГИЧЕСКИМ спобом и для финского, и для англ., и даже для ирландского с 16 данными и двумя ОТВЕТАМИ. Советую применять - получите удовольствие от процесса РЕШЕНИЯ.
Добавить комментарий