Prezentatsia_k_zaschite_Medvedev_O_S

1.

Государственное бюджетное общеобразовательное учреждение школа № 604
Пушкинского района Санкт-Петербурга имени Н.С. Майданова
(ГБОУ №604 Пушкинского района Санкт-Петербурга)
ИССЛЕДОВАТЕЛЬСКАЯ РАБОТА
на тему
«Оценка эффективности математических методов решения судоку»
Выполнил:
Медведев Олег Сергеевич
ученик 9 «Б» класса
Учитель-наставник:
Егорова Ольга Валерьевна
учитель информатики
Санкт-Петербург
2026

2.

Объектом исследования данной работы являются математические методы решения
головоломки судоку.
Предметом исследования выступает эффективность применения различных математических
методов для нахождения решения.
Целью работы является изучение и оценка эффективности математических методов решения
судоку с точки зрения объективных характеристик.
1.
2.
3.
4.
5.
6.
Для достижения поставленной цели необходимо решить следующие задачи:
Провести обзор литературных источников и интернет-ресурсов по классическим методам решения
судоку, изучить историю возникновения головоломки и её математическую сущность.
Выбрать несколько конкретных математических методов для анализа.
Реализовать метод backtracking на языке программирования Python, обеспечив возможность замера
времени работы.
Сформировать набор тестовых судоку разного уровня сложности (очень лёгкие, лёгкие, средние,
сложные, экспертные) для проведения объективного сравнения.
Запрограммировать измерение эффективности каждого метода, фиксируя время выполнения.
Провести сравнительный анализ полученных результатов, выявить сильные и слабые стороны
каждого подхода и определить наиболее эффективный алгоритм для разных классов входных
данных.

3.

Гипотеза исследования заключается в следующем: дедуктивные
методы, основанные на логических стратегиях, обеспечивают более
высокую скорость решения судоку по сравнению с простым перебором
на задачах средней и высокой сложности, однако уступают ему в полноте
— часть головоломок экспертного уровня остается нерешенной.
Переборный метод, несмотря на бóльшие временные затраты,
гарантирует нахождение решения для любой корректной головоломки.

4.

Судоку как математическая
задача об ограничениях
Набор ограничений — это правила игры.
Для судоку их три:
● В каждой строке все цифры должны
быть разными
● В каждом столбце все цифры должны
быть разными
● В каждом блоке 3×3 все цифры
должны быть разными
Классический судоку 9х9

5.

Уровни сложности судоку
Уровень сложности
Количество подсказок
1 (Очень лёгкий)
Более 46
2 (Лёгкий)
36–46
3 (Средний)
32–35
4 (Сложный)
28–31
5 (Экспертный)
17–27
Классификация уровней сложности судоку по количеству подсказок (составлено по: Maji, Jana, Pal, 2013)

6.

Методы решения судоку
1.
Переборные методы – алгоритмы, которые последовательно перебирают возможные варианты
заполнения клеток, а при возникновении тупика возвращаются назад и пробуют другие варианты. Они
гарантированно находят решение, если оно существует, но могут работать долго.
2.
Дедуктивные методы – способы, имитирующие мышление человека. Они не перебирают варианты, а
последовательно применяют логические правила, чтобы исключать невозможные цифры из кандидатов
или определять значения клеток. Такие методы часто называют «человеческими» стратегиями.
Переборный метод
Дедуктивный метод
Алгоритм поиска с возвратом (backtracking),
реализованный самостоятельно на языке Python.
Открытый решатель, реализующий набор логических
стратегий, доступный в репозитории пользователя
omerfarukeker на платформе GitHub.
Алгоритм последовательно заполняет пустые клетки,
перебирая цифры от 1 до 9, и при возникновении Код решателя был использован без изменений.
тупика возвращается к предыдущей клетке.
Измерялось время решения и фиксировался факт
успешного завершения (решена головоломка или
нет).

7.

Тестовый материал
100 судоку, сгруппированных по пяти уровням сложности (по 20 головоломок
каждого уровня). Классификация уровней основана на количестве изначально
заполненных клеток (подсказок).
Судоку Everest, который был разработан в 2012 году финским математиком Арто
Инкала, считающийся одним из самых сложных.
Для объективной оценки эффективности работы алгоритмов был выбран
временной критерий: время выполнения задачи (измеряемое в миллисекундах). Это
универсальный показатель, позволяющий напрямую сравнивать скорость различных
методов на одинаковом аппаратном обеспечении. Чем меньше время, тем
эффективнее алгоритм.

8.

Уровень
сложности
Количество
подсказок
Простой перебор
(backtracking)
(время в
миллисекундах)
Очень лёгкий
>46
15
12
20/20 (100%)
Лёгкий
36–46
37
38
20/20 (100%)
Средний
32–35
75
69
20/20 (100%)
Сложный
28–31
589
298
20/20 (100%)
Экспертный
17–27
2357
1785
18/20 (90%)
3596
1842
Судоку
Everest
Дедуктивный
решатель (время
в
миллисекундах)
Доля судоку,
решенных
дедуктивным
методом

9.

Выводы
1.
2.
3.
4.
5.
Сравнение на простых уровнях: На судоку с большим числом подсказок (легкие и средние) оба
метода показывают высокую скорость (сотые доли секунды). Разница в производительности
несущественна.
Эффективность дедуктивных методов: На сложных и экспертных уровнях дедуктивный
решатель в 1.6–2 раза быстрее переборного (например, 298 мс против 589 мс на сложном
уровне), что подтверждает выдвинутую гипотезу.
Главный недостаток дедуктивных методов: Дедуктивный метод не является полным. Он не
справился с 5% (2 из 20) экспертных судоку, так как чистая логика бессильна в ситуациях,
требующих «угадывания».
Главное преимущество перебора: Метод поиска с возвратом (backtracking) гарантированно
находит решение для любой корректной головоломки, что делает его абсолютно надежным, хотя
и более медленным.
Судоку «Everest» было решено дедуктивным методом почти вдвое быстрее (1842 мс vs 3596 мс),
что доказывает возможность применимости дедуктивных методово даже к сверхсложным
задачам.

10.

Заключение
Гипотеза, сформулированная во введении, полностью подтверждается:
дедуктивные методы обеспечивают более высокую скорость решения судоку
различной сложности, однако не гарантируют решения абсолютно всех
представленных головоломок; переборный метод, будучи медленнее, обладает
свойством полноты и решает любую корректную задачу.
Полученные результаты хорошо согласуются с данными независимых
исследований, например, с работой Бхаттараи с коллегами, где показано, что
эвристические подходы превосходят простой перебор по скорости в 1,3–2,9 раза в
зависимости от сложности (Bhattarai et al., 2025).
Выбор оптимального метода решения зависит от конкретной задачи и
доступных вычислительных ресурсов: если требуется быстрое решение и допустим
риск неудачи, предпочтительнее дедуктивный метод; если же необходима гарантия
результата, следует применять перебор.

11.

СПАСИБО
ЗА
ВНИМАНИЕ
Медведев Олег Сергеевич
ученик 9 «Б» класса