Решение судоку быстро

Знаменитая японская головоломка существует с 19 века. Однако только в конце 90-х была написана компьютерная программа для быстрого создания головоломок, и даже позже, в 2006 году, была разработана быстрая техника решения головоломок судоку произвольного размера. Этот метод сводит судоку к другой проблеме и использует эффективную структуру данных для поиска решения. Давайте взглянем!

Решение судоку

Если мы хотим решить судоку методом перебора, наш алгоритм должен будет пробовать каждое доступное число во всех пустых ячейках. Такой алгоритм имел бы сложность выполнения O (N ^ (N²)), где n - размер головоломки судоку. Для головоломки судоку размером 9x9 (N = 9) алгоритм будет выполнять 2 * 10⁷⁷ операций, чтобы найти решение. Это было бы непрактично. На практике время выполнения будет варьироваться в зависимости от сложности самой головоломки и количества вариантов для каждой пустой ячейки. Например, головоломка из 17 подсказок с диагональной симметрией - одна из самых сложных для решения из-за большого количества кандидатов и ответвлений.

Приведение к точному покрытию

Давайте рассмотрим следующую проблему: для двоичной матрицы из N строк и M столбцов найдите подмножество строк, в которых сумма каждого столбца равна 1. Таким образом, допустимое решение будет иметь по одной единице в каждом столбце. Это известно как проблема точного покрытия, которая является NP-полной. Это означает, что любую проблему в NP можно свести к проблеме точного покрытия, что и делает NP-полные проблемы такими интересными. Раскраска графов, двухмерный рюкзак, мозаика и судоку - все это сводится к задаче точного покрытия.

Представим судоку в терминах задачи о точном покрытии. Мы преобразуем 4 ограничения головоломки Судоку в двоичную матрицу, так что решение точной матрицы покрытия будет иметь взаимно однозначное соответствие решению головоломки Судоку. Ограничения для любой головоломки судоку:

  • В каждой строке номер может появляться только один раз.
  • Для каждого столбца число может появиться только один раз.
  • Для каждой области (маленький квадрат) число может появиться только один раз.
  • В каждой ячейке может быть только одно число.

В нашей двоичной матрице каждый столбец будет представлять ограничение для ячейки судоку, а каждая строка будет представлять возможное присвоение ячейки судоку номеру кандидата. Для судоку 9x9 двоичная матрица будет иметь 4 столбца x 9² и 9³ строк. Цель состоит в том, чтобы найти такое подмножество строк, чтобы в каждом столбце была одна единица, удовлетворяющая всем ограничениям по всем столбцам, которые будут отображаться в решении головоломки судоку.

Алгоритм X

Чтобы решить точную проблему покрытия, мы будем следовать методу проб и ошибок Дональда Кнута под названием Алгоритм X. Метод перебирает столбцы двоичной матрицы, рекурсивно пытаясь выбрать строки, которые их покрывают.

AlgorithmX():
  If Matrix has no Columns
    Terminate with the current solution
  Assign C to the first column in Matrix
  For each Row R in where Matrix[R][C] = 1
    AddRowToSolution(R) and CoverRow(R)
    Recursively call AlgorithmX() on the modified Matrix
    RemoveRowFromSolution(R) and UncoverRow(R)
CoverRow(R):
  For each Column C where Matrix[R][C] = 1
    For each Row L where Matrix[L][C] = 1
      For each Node N in L
        Cover(N)
    Remove C from Matrix
UncoverRow(R):
  For each Column C where Matrix[R][C] = 1
    For each Row L where Matrix[L][C] = 1
      For each Node N in L
        Uncover(N)
    Un-remove C from Matrix

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

Танцы Links

Что делает алгоритмическую технику замечательной? Возможно, когда это значительно сократит временную сложность решения интересной задачи. Или когда это делается с помощью простого, интуитивно понятного и изящного трюка. Или, может быть, потому, что это поддерживается рок-звездой компьютерных наук и алгоритмов. Если так, то Dancing Links - это здорово!

Первый шаг к улучшению наивной версии - осознать, что на практике матрица будет очень разреженной. На этапе сокращения давайте проанализируем количество единиц в каждой строке и каждом столбце. Поскольку каждая строка представляет собой присвоение номера кандидата ячейке, для головоломки судоку 9x9 в каждом столбце должно быть ровно 9 единиц. Точно так же в каждой строке будет только 4 единицы, по одной для каждого из 4 ограничений. Это мотивирует другое представление, которое использует этот уровень разреженности.

Вместо того, чтобы хранить матрицу как традиционный двумерный массив, мы будем использовать тороидальный двусвязный список. Каждая ячейка в матрице будет узлом в связанном списке. Каждый узел будет иметь ссылки на своих верхних, нижних, правых и левых соседей. Это позволяет нам эффективно закрывать и раскрывать строки, поскольку хранятся только единицы. Поиск единиц в любой строке или столбце превращается в операцию O (1) вместо O (N).

Теперь удаление (закрытие) узла с его позиции будет выглядеть так:

Cover(node):
  Assign node.left.right to node.right
  Assign node.right.left to node.left

При возврате (раскрытии) узла в исходное положение он будет выглядеть так:

Uncover(node):
  Assign node.left.right to node
  Assign node.right.left to node

Термин «танцующие ссылки» был выбран потому, что суть алгоритма напоминает танец узлов, когда они обмениваются ссылками.

Реализация

Мы протестировали этот подход, решая головоломки-судоку размером 16x16, против которых не побоялись бы решатели с возвратом и наивные реализации. Однако наша реализация находит решение для данной головоломки в среднем менее чем за 300 миллисекунд.

Даже быстрее

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

Ресурсы

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