ПРИМЕНЕНИЕ ТЕОРИИ ВЕРОЯТНОСТЕЙ В ОПТИМИЗАЦИИ ПОИСКА РЕШЕНИЙ СУДОКУ

APPLICATION OF PROBABILITY THEORY TO OPTIMIZATION OF SUDOKU SOLUTION SEARCH

Shikula Anastasia Vyacheslavovna

Student, Department of Management, Belarusian State University of Informatics and Radioelectronics,

Belarus, Minsk

Stoliar Julia Nikolaevna

Student, Department of Management, Belarusian State University of Informatics and Radioelectronics,

Belarus, Minsk

Fedosyuk Lyudmila Petrovna

scientific supervisor, Senior Lecturer, Belarusian State University of Informatics and Radioelectronics,

Belarus, Minsk

АННОТАЦИЯ

В статье исследуется проблема эффективного решения судоку — NP-полной комбинаторной задачи, для которой традиционные алгоритмы перебора с возвратом часто оказываются неэффективными из-за экспоненциального роста вычислительной сложности. Основной недостаток существующих подходов заключается в отсутствии интеллектуальной стратегии выбора очередной ячейки и подходящего числа-кандидата, что приводит к частым тупиковым ветвлениям и необходимости откатов.

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

ABSTRACT

The article examines the problem of efficiently solving Sudoku - an NP-complete combinatorial problem for which traditional backtracking algorithms often prove ineffective due to exponential growth in computational complexity. The main drawback of existing approaches lies in the lack of an intelligent strategy for selecting the next cell and appropriate candidate number, leading to frequent dead-end branches and the need for backtracking.

A new probabilistic approach is proposed that transforms classical exhaustive search into a controlled process using heuristics based on probability theory. The method involves calculating probabilistic estimates for candidate numbers in each empty cell, which helps reduce the number of erroneous branches and improves the overall algorithm efficiency.

Ключевые слова: Судоку, NP-полная задача, алгоритм перебора с возвратом, вероятностные эвристики, оптимизация вычислений.

Keywords: Sudoku, NP-complete problem, backtracking algorithm, probabilistic heuristics, computational optimization.

Судоку, несмотря на простоту правил, представляет собой NP-полную комбинаторную задачу размещения. Классические компьютерные алгоритмы решения, такие как метод перебора с возвратом, основанные на последовательных подстановках и проверках, часто оказываются неэффективными для сложных пазлов из-за экспоненциального роста вычислительной сложности.

Основной недостаток традиционного подбора заключается в отсутствии интеллектуальной стратегии выбора на двух уровнях: выбора очередной ячейки для обработки и выбора цифры-кандидата внутри ячейки. Это приводит к частому попаданию в тупиковые ветви вычислений, требующие возврата. В данной статье предлагается использовать вероятностный подход для управления работой алгоритма перебора, преобразуя его в более целенаправленный процесс, управляемый эвристическими оценками, основанными на теории вероятностей.

Пусть G — текущее состояние частично заполненной сетки судоку. Для каждой пустой ячейки (i, j) определяется множество кандидатов  — цифр, которые могут быть помещены в ячейку без нарушения правил на текущем этапе.

Вместо равноправного рассмотрения всех кандидатов, для каждой цифры d в ячейке (i, j) вычисляется оценка правдоподобия P(d | i, j, G) — вероятность того, что цифра d должна находиться в данной позиции при текущем состоянии сетки.

Вероятность вычисляется на основе анализа связанных областей (строка, столбец, блок). Формула имеет вид:

где:

-  — количество ячеек в строке i, куда цифра d может быть потенциально размещена;

-  — количество ячеек в столбце j, куда цифра d может быть потенциально размещена;

-  — количество ячеек в блоке, содержащем (i, j), куда цифра d может быть потенциально размещена.

Данная формула отражает «степень свободы» цифры в связанных областях: чем меньше альтернативных размещений, тем выше вероятность корректности данной позиции.

Для количественной характеристики неопределённости состояния ячейки используется энтропия по Шеннону. Энтропия ячейки (i, j) вычисляется как:

где  — нормализованная вероятность кандидата d, полученная из P(d | i, j, G).

Низкое значение энтропии соответствует ячейке с доминированием одного или нескольких вариантов, высокое — ячейке с равномерным распределением вероятностей между кандидатами.

Для преобразования классического алгоритма перебора с возвратом в целенаправленный поиск предлагается двухуровневая стратегия выбора, применяемая на каждом шаге вычислений.

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

Стратегия выбора кандидата. Для выбранной ячейки-кандидата цифры проверяются в строгом порядке убывания их вычисленных вероятностей . Эта стратегия основана на предпосылке, что кандидат с более высокой вероятностью с большей вероятностью является корректным для данной позиции. Таким образом, перебор начинается с наиболее перспективных вариантов, что статистически увеличивает шанс движения по корректной ветви дерева поиска с первого раза и минимизирует количество тупиковых ветвей.

Предложенный метод является естественным развитием и обобщением классической эвристики «Minimum Remaining Values» (MRV). Если MRV оперирует лишь количеством кандидатов в ячейке (что эквивалентно предположению о равномерном распределении их вероятностей), то наш вероятностный подход учитывает более глубокие, глобальные зависимости через взвешенное распределение вероятностей. Энтропия  в данном контексте служит универсальной мерой неопределенности, которая учитывает не только число кандидатов, но и степень концентрации вероятностной массы.

Стратегия выбора ячейки с минимальной энтропией реализует принцип «наибольшего информационного выигрыша». Каждое такое присвоение значения приносит максимум информации для системы, последовательно сужая пространство поиска. В сочетании с упорядочиванием кандидатов по убыванию вероятности это создает мощный эвристический механизм, который направляет алгоритм по наиболее перспективным путям в дереве решений, кардинально сокращая количество необходимых возвратов по сравнению с ненаправленным перебором.

Хотя в худшем случае задача решения судоку остается экспоненциальной, предложенный вероятностный подход демонстрирует значительное повышение эффективности на практике для большинства нетривиальных пазлов.

Ключевые преимущества метода:

- уменьшение количества возвратов (направленный выбор сокращает количество анализируемых тупиковых ветвей);

- сохранение полноты (метод сохраняет полноту охвата пространства решений);

- универсальность (подход не требует фундаментальной переформулировки задачи и может быть интегрирован в существующие реализации).

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

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

Список литературы:

1. Поиск с возвратом в решении типичных задач на собеседовании [электронный ресурс] — Режим доступа. — URL: https://medium.com/nuances-ofprogramming/%D0%BF%D0%BE%D0%B8%D1%81%D0%BA-%D1%81-%D0%B2%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%BE%D0%BC%D0%B2%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B8%D1%82%D0%B8%D0%BF%D0%B8%D1%87%D0%BD%D1%8B%D1%85-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87-%D0%BD%D0%B0-%D1%81%D0%BE%D0%B1%D0%B5%D1%81%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B8-fc60a32ff1a6 (дата обращения 25.10.2025)
2. Тайны судоку и не только [электронный ресурс] — Режим доступа. – URL: https://libeldoc.bsuir.by/bitstream/123456789/35280/1/Karymov_Tayny.pdf (дата обращения 25.10.2025)
3. Sudoku as a Constraint Problem [электронный ресурс] — Режим доступа. – URL: https://ai.dmi.unibas.ch/_files/teaching/fs21/ai/material/ai26-simonis-cp2005ws.pdf (дата обращения 25.10.2025)