Особенности решения концептуальной модели задачи решающего комплекса
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Вµё применения. В случае ошибки программа бы рекурсивно перешла дальше и так до тех пор, пока не кончились бы все формулы. После того, как шаблон для t был найден, идёт вторая попытка применения шаблона для x. В случае успеха происходит вывод.
Следует отметить, что процесс поиска вспомогательных концептуальных задач последовательный, так как интерпретатор языка выводит ошибку при нахождения первого несоответствия и не просматривает строку дальше.
Таким образом, можно решать задачи практически любой сложности. Глубину рекурсии также можно регулировать во избежание попадания в бесконечный цикл. Можно выделить две базовые задачи эксперта по моделированию. Первая - это наполнение базы данных и знаний (по сути - математических формул) для предметной области. Вторая - правильное описание данных для нахождения решения данной конкретной задачи.
Принципиальная схема решения:
Рис.8. Принципиальная схема работы программы
Судоку
Судоку (яп. ?? су:доку) - популярная головоломка-пазл iислами. В переводе с японского су - цифра, доку - стоящая отдельно. Иногда судоку называют магическим квадратом, что в общем-то не верно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку - популярный вид досуга.
Игровое поле представляет собой квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), так как незаполненное игровое поле не имеет смысла. В зависимости от того, сколько клеток уже заполнены, конкретную судоку можно отнести к лёгким или сложным.
Существует несколько методов решения судоку. Условно их можно разделить на две категории - логические и вычислительные. К вычислительным методам относится метод полного перебора (BruteForce). Логические - метод одиночного квадрата, закрытого кандидата, голой и скрытой пары, крыло, slicing and dicing и методы предположений различного уровня.
Методы составления судоку начинаются с составления правильного латинского квадрата. Дальнейшее составление идёт либо постепенным вычёркиванием чисел и проверкой на возможность решения, с оценкой сложности по количеству итераций и применяемому методы, либо открытием определённого числа закрытых клеток. Причём как в первом, так и во втором случае вообще говоря судоку может получиться недетерменированным (то есть допускающим несколько вариантов решения для одних и тех же исходных данных).
Исходный вид разработанной программы при решении судоку такой:
Рис.9. Вид окна программы в режиме решения судоку
Решение судоку
Сначала рассмотрим решение при помощи вспомогательных концептуальных моделей. При нажатии на эту кнопку вызывается окно, в котором можно переключать просмотр по столбцам, строкам или малым квадратам. Элементами вспомогательной концептуальной модели являются непосредственно столбцы, строки или малые квадраты.
Рассмотрим на примере простого судоку:
Рис.10. Пример простого судоку
Рис.11. Одна из вспомогательных концептуальных моделей для простого судоку
При нажатии на кнопку Решить текущие вспомогательные модели программа выполнит решение для выделенной вспомогательной концептуальной модели, то есть в нашем случае попытается разрешить все квадраты.
Разрешение вспомогательной модели возможно только в том случае, если в данном конкретном элементе (в нашем случае это квадрат с левым верхним углом A4) отсутствует только одна цифра. В данном случае это верно, поэтому после нажатия данной кнопки мы получим результат:
Рис.12. Решение всех возможных концептуальных моделей для малых квадратов
В случае нажатия на кнопку Разрешить все вспомогательные модели программа в бесконечном цикле будет проходить по всем возможным вспомогательным моделям до тех пор, пока они имеют решение. Принципиально это выглядит следующим образом:
Рис.13. Принципиальная схема разрешения вспомогательных концептуальных моделей
Метод полного перебора действует следующим образом:
.Ведётся поиск первого вхождения 0 (то есть пустой клетки)
.Если вхождений нет, значит мы получили решение
.Определяются цифры, которые могут входить в данную клетку (с учётом столбца, строки и малого квадрата). Определение осуществляется функцией:
c = [s[j] for j in range(81)not ((i-j)%9 * (i//9^j//9) * (i//27^j//27 | (i%9//3^j%9//3)))]
1.(i-j)%9 - вхождение в столбец
.(i//9^j//9) - вхождение в строку
.(i//27^j//27 | (i%9//3^j%9//3)) - блок из трёх строк
.В случае вхождения получается 0
.Для всех чисел, которые могут стоять в данной строке рекурсивно вызывается функция перебора, где на месте пустой клетке стоит некоторое число
.Если нет чисел, которые мы можем вставить в данную клетку, значит метод зашёл в тупик и следует выход из рекурсии на шаг выше.
Несмотря на то, что существует порядка финальных вариантов судоку (то есть всех возможных расположений), метод брутфорса может быть полезен для решения задачи судоку на компьютере. Действительно, для указанного простого судоку подобный метод перебора получил решения за 0.0163с.
Рис.14. Пример работы алгоритма полного перебора для решения простого судоку
Но существуют задачи, которые алгоритм полного перебора будет р