Ответ в теме: Решение судоку на Prolog

      Комментарии к записи Ответ в теме: Решение судоку на Prolog отключены
#2573

В коде используется библиотека CLPFD (Constraint Logic Programming over Finite Domains). Она подключается в первой строке с помощью команды:
:- use_module(library(clpfd)).
Используемые предикаты из библиотеки:

  1. append – Объединение списков
  2. all_distinct – Истина, если все числа в списке имеют разные значения
  3. maplist – Истина, если операция была успешно применена ко всем элементам списка
  4. transpose – Транспонирование
  5. label – Позволяет построить только одно конкретное значение в том случае, если есть более одного решения

Программа работает по следующему алгоритму:

  • Предикат Sudoku(Rows) принимает матрицу, представленную в виде набора списков (строк).
  • Строки объединяются функцией append.
  • С помощью maplist вызывается предикат all_distinct, который возвращает истину в случае, если числа в строке (элементе Rows) встречаются один раз.
  • Матрица транспонируется чтобы заменить строки столбцами, с транспонированной матрицей еще раз выполняется проверка (фактически проверятся столбцы исходной матрицы).
  • С помощью предиката blocks матрица преобразуется в блоки 3×3 и выполняется проверка уникальности чисел в блоке.
  • Снова используется maplist для вызова предиката label для строк. label гарантирует, что все числа имеют одно конкретное значение, но только в том случае, если есть более одного решения судоку

Алгоритм работы функции blocks:

  • предикат истинен, если он получает три пустых списка в качестве входных. Это точка выхода для рекурсии;
  • blocks имеет непустое значение. С помощью оператора разделения списка на голову и хвост | разбиваются данные строк в первых трех элементах и хвосте, которые используются позже;
  • имеется получился блок 3×3, включающий три элемента из каждой строки, изначально взятой из blocks в sudoku. Опять происходит проверка, что число повторяется только один раз;
  • рекурсивно обрабатывается остальная часть списков (пока не получится пустых списков).