Разрешение концептуальных моделей

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

Рассмотрим на примере простого судоку:

 

При нажатии на кнопку «Решить текущие вспомогательные модели» программа выполнит решение для выделенной вспомогательной концептуальной модели, то есть в нашем случае попытается разрешить все квадраты.

Разрешение вспомогательной модели возможно только в том случае, если в данном конкретном элементе (в нашем случае это квадрат с левым верхним углом A4) отсутствует только одна цифра. В данном случае это верно, поэтому после нажатия данной кнопки мы получим результат:

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

Метод полного перебора

Метод полного перебора действует следующим образом:

1. Ведётся поиск первого вхождения 0 (то есть пустой клетки)

2. Если вхождений нет, значит мы получили решение

3. Определяются цифры, которые могут входить в данную клетку (с учётом столбца, строки и малого квадрата). Определение осуществляется функцией:

c = [s[j] for j in range(81)

if not ((i-j)%9 * (i//9^j//9) * (i//27^j//27 | (i%9//3^j%9//3)))]

1. (i-j)%9 – вхождение в столбец

2. (i//9^j//9) – вхождение в строку

3. (i//27^j//27 | (i%9//3^j%9//3)) – блок из трёх строк

4. В случае вхождения получается 0

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

5. Если нет чисел, которые мы можем вставить в данную клетку, значит метод зашёл в тупик и следует выход из рекурсии на шаг выше.

Несмотря на то, что существует порядка финальных вариантов судоку (то есть всех возможных расположений), метод брутфорса может быть полезен для решения задачи судоку на компьютере. Действительно, для указанного простого судоку подобный метод перебора получил решения за 0.0163с.

Но существуют задачи, которые алгоритм полного перебора будет решать очень долго. Возьмём для примера судоку под названием «Star Burst Leo»

Было оценено, что для решения данного судоку потребуется 641 580 331 итерация, причём в данном случае в итерации не входит процесс поиска цифр, которые можно внести в данную клетку.

На рисунке 16 показано распределение числа заполненных клеток (ось ординат) от уровня рекурсии (ось абсцисс). Таким образом можно оценить, что процесс перебора доходит до 72 заполненных клеток, а затем встречает несоответствие и ему приходится возвращаться, причём мы видим чёткие полосы в районе 33, 43 и 60 заполненных клеток.

Логические методы решения

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

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

Все методы рассматриваются в статье [2], но здесь я опишу несколько из них.

Первый метод – Х-крыло.

«X-крыло» — позиция, когда один из кандидатов дважды (и только дважды) встречается в двух строчках головоломки. Эти кандидаты должны входить в две колонки, что обеспечивает формирование прямоугольного Х-крыла. Также две колонки с двумя (и только с двумя) клетками, которые содержат одинаковых кандидатов (входящие в две строки) также формируют X-крыло. Эти четыре клетки — единственные возможные места расположения для «настоящих» кандидатов в этих строках или колонках. Другие подобные кандидаты, расположенные по периметру прямоугольника, образованного «настоящими» кандидатами, должны быть удалены. Возможно эта комбинация была названа X-крылом потому, что

Рассмотрим пример решения Х-крыла (рисунок вверху). Как видим, для легкости восприятия из кандидатов отображены только шестерки (был применен фильтр кандидатов — программа Simple Sudoku это умеет делать).

Синие и ярко-зеленые ячейки формируют классическое «X-крыло» — первая и девятая строчки имеют только по две ячейки с кандидатом 6, их разделяют две колонки (седьмая и восьмая), кандидаты образуют прямоугольник. «Настоящих» кандидатов представляют синие, или ярко-зеленые ячейки. Потому другие кандидаты в шестой и девятой колонках нужно удалить (они выделены желтым контуром).

 

 

Slicind and dacing

Рассмотрим метод slicing and dacing на примере:

На первом шаге рассматриваются пересечения столбца и строки для цифры 1 в рамках квадрата G1-I3. Получается, что 1 может стоять либо на позиции H1 либо на позиции I1.

На основе полученного результата на первом шаге просматривается полученная строка. В квадрате D1-F3 с учётом стоящей на позиции E8 единицы и полученной на первом шаге строки остаётся только одна позиция – D2. Таким образом, после работы алгоритма получаем судоку:

Аналогичным образом можно получить единицы во всех остальных малых клетках.

Метод предположений похож на метод полного перебора. Но применяется он после применения вышеуказанных методов. Рассмотри на примере:

При решении стандартными логическими методами (скрытые пары, скрытые квадраты и т. п.) решение не найдено:

Но мы видим, что в клетках B3 и C3 может стоять только пара 46. Алгоритм делает предположение, что стоит в B3 стоит 4, доходит до несоответствия, ставит 6 и получает результат:

Таким образом исходное судоку разрешено.

Блок-схема алгоритма выглядит следующим образом:

Составление судоку

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

Составление открытием

Но несмотря на то, что цифры из доски выполняется в порядке, обратном заполнению, всё равно возможно получение недетерменированного судоку и данную проблему разрешить невозможно.

 

Решение вычёркиванием

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