Пролог: краткое введение

Язык, созданный для решения головоломок!

Пролог — довольно интересный язык программирования, который заставит вас мыслить совершенно иначе, чем вы привыкли, независимо от того, исходите ли вы из процедурной, функциональной и/или объектно-ориентированной парадигмы.

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

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

Основы

Атомы, или константы, начинаются со строчных букв или представляют собой целые числа: кот, джон, 1, 2, 3, машина. Переменные начинаются с прописных букв или символов подчеркивания: X, Y, Z, Result, _var, _1. До сих пор мы видели термины. У нас также могут быть составные термины. Давайте используем составной термин для объявления факта:

student(saif, nus).
student(saif, uoft).

Первый факт гласит, что saif является student из nus. Обратите внимание на точку в конце «предложения». Мы можем вставить больше фактов в программу. Мы называем это предложением, где student является предикатом.

Теперь мы можем выполнить запрос к этим предложениям, используя переменную. Давайте посмотрим, как это делается.[Строки с ?- — это то, что я печатаю, % — начало комментариев, остальное — то, что говорит Пролог. ]

?- student(saif, X).
X = nus ;
X = uoft.

Пролог вычислил, что X должен быть либо nus, либо uoft!

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

Отношения против функций

Прежде чем углубиться, полезно сделать шаг назад и понять, что мы неопределяем функции в Прологе. Мы объявляемотношения. Какая разница?

Допустим, у нас есть функция add(a, b) в *insert_favorite_language*. Эта функция принимает 2 целых числа и дает нам результат. Таким образом, add(1, 2) вернет 3.

В Прологе вы бы запросили add(1, 2, R), и язык сказал бы вам, что R = 3. «Э-э, ладно…» Я слышал, вы говорите. Но это всего лишь один из способов выполнить запрос; мы можем запустить его еще 3 способами:

% checking / assertion
?- add(1, 2, 3).
true.
?- add(1, 2, 4). 
false. 

% subtracting!
?- add(X, 2, 3). 
X = 1.

% and enumerating all possible answers!
?- add(X, Y, 3). 
... (infinitely many combinations of X and Y make 3!)

Сладкий! Хотя кажется, что этот последний шаг занимает ужасно много времени :shrugs: Мы можем изменить его, чтобы он занимал меньше времени, предоставив Prolog больше фактов о Vars.

?- add(X, Y, 3), X > -1, Y > -1. 
X = 0
Y = 3; 
X = 1
Y = 2; 
X = 2
Y = 1; 
X = 3
Y = 0; 

Обратите внимание, здесь я впервые использовал оператор AND: это запятая. Вскоре мы увидим оператор ИЛИ в виде точки с запятой.

Логика, наконец!

% example courtesy, CS2104, NUS
father(john, mary).
father(john, tom).
father(kevin, john).
mother(eva, tom).
mother(eva, mary).
mother(cristina, john).
male(john).
male(kevin).
male(tom).
female(eva).
female(cristina).
female(mary).

И давайте спросим об этих фактах:

% Who's mary's father?
?- father(X, mary).
X = john.
% Who are eva's children?
?- mother(eva, C).
C = tom ;
C = mary.
% Who is eva's daughter? 
?- mother(eva, C), female(C).
C = mary.

Давайте научим Пролог еще кое-чему о том, как работают семьи.

daughter(X,Y) :- female(X), parent(Y,X).
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
brother(X,Y) :- male(X),sibling(X,Y).
% first use of OR and HORN CLAUSE
parent(X, Y) :- father(X, Y); mother(X, Y).
% prolog has the standard mathematical operators
sibling(X,Y) :- parent(Z,X), parent(Z,Y), X\==Y.

:- обозначает «Оговорку о рогах». Я прочитал это как намек. Например, я прочитал родительское предложение как «ЕслиX является отцом Y ИЛИ X является матерью Y, тоX является родителем Y».

Мы тоже можем делать рекурсии! Далее говорится, что предком Y является родитель Y X или Z (где Z — предок X).

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).

Мы должны быть осторожны; мы можем застрять в бесконечном цикле с левой рекурсией в следующем примере:

% DO NOT DO THIS 
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- ancestor(Z,Y),parent(X,Z).

НО КАК? !— Объединение и разрешение

Невероятная способность Пролога отвечать на вопросы (даже на такие простые, как этот) исходит из его алгоритмов Разрешения и Объединения.

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

Затем Пролог возвращается к квадрату 1 и снова пробует его со всеми другими возможными значениями для каждой переменной, по существу выполняя поиск в глубину, пока не исчерпает все пространство поиска. Этот процесс ответа на запрос называется разрешением. Все, что можно доказать, является правдой; все остальное ложно (предположение о замкнутом мире).

Списки

Нам нужно узнать еще кое-что, прежде чем запачкать руки настоящими программами на Прологе. Во-первых, списки.

[this, [], is, a, random_term(X), lst].
% joining 2 lists together
append([], Y, Y). 
append([X|Xs], Y, [X, Rs]) :- append(Xs, Y, Rs).

Если вы внимательно посмотрите на отношение добавления, то увидите, что оно использует сопоставление с образцом в стиле Haskell и образец-накопитель. Вы обнаружите, что это естественный способ мышления, если вы пришли из функционального языка. [X|Xs] используется для представления списка, состоящего из 2 частей: X — начало списка, а Xs — остальная часть списка. 2 строки в основном говорят:

• Если первый список пуст, результатом будет второй.
• В противном случае результатом будет голова первого списка + результат соединения хвоста первого списка со всем вторым списком.

Давайте запустим несколько запросов с нашей новой функцией добавления:

?- append([1,2,3],[4,5],Z).
Z = [1,2,3,4,5]. 
% computing the difference of 2 lists
?- append([1,2,3],Y,[1,2,3,4,5]).
Y = [4,5]
% splitting a list
?- append(X,Y,[1,2]).
X=[], Y=[1,2];
X=[1], Y=[2];
X=[1,2], Y=[].
% finding prefix of a list (_ means I don't care about this). 
?- append(X,_,[1,2,3]).
X=[]; X=[1]; X=[1,2]; X=[1,2,3].

Конечно, некоторые из этих основных отношений были определены для вас. Вы можете посмотреть реализацию reverse() из SWI-Prolog здесь. Вот вам небольшая головоломка. Каков результат reverse(X, X). ?

Давайте свяжем это с Резолюцией и Объединением. Рассмотрим отношение sel(elem, […]), которое принимает список и сообщает нам, принадлежит ли элемент этому списку:

Управление возвратом с помощью оператора Cut

Рассмотрим отношение, которое принимает список и удаляет дубликаты:

remDupl([], []). 
remDupl([H|T], R) :- sel(H, T), remDupl(T, R).
remDupl([H|T], [H|R]) :- not(sel(H, T)), remDupl(T, R).

Довольно просто. Первая строка — базовый вариант. Вторая строка говорит, что если H найдено в T, отбросить его. Третья строка говорит, что если H не найдено в T, то добавить H к результату и продолжить рекурсию.

На самом деле мы управляем ветвью дерева поиска, используя это первое предложение sel(). Оказывается, это повторяющийся вариант использования в Прологе, поэтому мы используем оператор «вырезать», обозначаемый !. Прочитайте это так: если вы выберете эту ветвь, не беспокойтесь о других вариантах на этом уровне.

remDupl([], []). 
remDupl([H|T], R) :- sel(H, T),!, remDupl(T, R). 
remDupl([H|T], [H|R]) :- remDupl(T, R).

Более лаконично? Читабельнее? Вам решать. Я просто говорю, что он существует.

Математические операторы и крошечная задачка.

У нас также есть все обычные математические операторы: ‹, ›, ≥, ≤, =\=, =:=, +, -, *. Давайте попробуем написать факториальную функцию:

% declaration
fact(0, 1). 
fact(N, R) :- N>0, M is N-1, fact(M, R1), R is R1*N. 

fact(15, R) правильно указывает, что R = 1307674368000. Не верите мне? Я подожду.

К сожалению, `fact(X, 120)` не даст нам 5. Проблема в том, что математические операторы можно использовать только одним способом. Поэтому, когда мы говорим M is N-1 , N должно быть известно, чтобы это работало :(

Мы решим эту проблему, используя мощный модуль Constraint Logic Programming, который делает кодирование на Прологе гораздо более интересным.

Линейное программирование с ограничениями

И последнее, что вы должны знать, чтобы сделать Prolog полезным: решение ограничений. Многие головоломки, которые мы решаем в реальной жизни, основаны на конечной области. Если вы знакомы с линейным программированием (или изучали линейную алгебру), вы знаете, как мы сужаем пространство поиска для набора уравнений (до такой степени, что грубая сила становится практичной).

Пакет довольно прост в использовании: в нем есть операторы, похожие на знакомые вам математические операторы (только с префиксом #), и несколько довольно изящных соотношений. Каноническим примером модуля CLP является головоломка ОТПРАВИТЬ+БОЛЬШЕ=ДЕНЬГИ. Давайте посмотрим на код здесь и поймем, что он делает. Если вы не знакомы, Загадка «отправить больше денег — типичный пример проблемы ограничений. Это равнозначно назначению разных цифр от 0 до 9 переменным [S,E,N,D,M,O,R,Y] таким образом, что SEND+MORE=MONEY”:

use_module(library(clpfd)).
sendmoremoney(Vars) :-
    Vars = [S,E,N,D,M,O,R,Y],
    Vars ins 0..9,
    S #\= 0,
    M #\= 0,
    all_different(Vars),
                 1000*S + 100*E + 10*N + D
    +            1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y.

Мы видим отношение ins из clp, говорящее, что все переменные в списке Vars должны принимать значения от 0 до 9. Следующие 2 строки говорят, что первые цифры слов не могут быть 0 (решение становится тривиальным). В следующей строке используется отношение all_different, чтобы убедиться, что все буквы получают разные назначения. Последняя строка гарантирует, что Пролог понимает, что положение буквы имеет значение и что два слова складываются (+) в (#=) ДЕНЬГИ.

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

% just note that the recursive call comes last. 
cfact(0, 1). 
cfact(N, R) :- N #> 0, M #= N-1, R #= N*R1, cfact(M, R1).

Решатель судоку

Все еще здесь? Крутое печенье, ты. Ладно, пора погрузиться в настоящую проблему. Сделаем решатель Судоку. О, подожди. В SWI-Prolog уже есть один. Не беспокойтесь, решение для судоку 9 * 9 с 3 * 3 блоками. Мы обобщим его на любую N*N судоку с блоками B_R*B_C. Давайте посмотрим на исходный код решателя и посмотрим, что нам нужно изменить:

sudoku(Rows) :-
        length(Rows, 9), 
        maplist(same_length(Rows), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).

• Первое предложение гарантирует, что у нас есть 9 строк.
• Второе предложение имеет отношение maplist(). Он принимает каждую из 9 строк и предоставляет их каррированной функции same_length(Rows). Поскольку мы имеем дело с квадратными матрицами, эта строка в основном говорит: размер каждой строки должен быть равен количеству столбцов.
• Отношение append/2 берет строки и разворачивает их, чтобы создать массив из 81 элемента с именем Vs. Каждый элемент в Vs должен быть от 1 до 9 (только целые числа). Помните, если это так, каждый элемент в Rows (т.е. матрица) также должен быть от 1 до 9.
• В следующей строке снова используется список карт. В нем говорится: «Для каждой строки в строках каждый элемент в строке должен быть отличным».
• Транспонировать строки в столбцы. Мы запускаем тот же список карт. Это гарантирует, что все столбцы также различны! Умная.

На данный момент мы убедились, что все строки и столбцы имеют номера от 1 до 9, и ни один номер не повторяется ни в одном столбце/строке. Последнее, что нам нужно сделать, это убедиться, что ни одно число не повторяется в мини-сетках 3*3. Вот что делает оставшаяся часть отношения:

• Затем мы даем каждой строке имя: As, Bs, Cs и так далее.
• Затем мы говорим, что первые 3 строки составляют блок. Следующие 3 составляют еще один блок. И последние 3 составляют последний блок.

Хорошо, а что такое блок? Рад, что вы спросили.

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
        all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
        blocks(Ns1, Ns2, Ns3).

• Блок состоит из 3 списков по 9 элементов в каждом. Пустые списки на всех 3 действительны.
• Чтобы блок был действительным, первые 3 элемента каждого списка должны составлять список, в котором каждый элемент отличается. И это условие должно выполняться для остальных оставшихся элементов каждого списка. Гений!

Давайте объявим проблемную сетку 9x9, редко заполненную, и посмотрим, какое решение предлагает Пролог:

problem(1, [[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

% Rows represent the grid of problem 1, where _ denotes unknown. 
% The given numbers give additional constraints. 
% Make sure you fill up the unknowns with the rules described in 
% sudoku. 
% After that, print each row. 
?- problem(1, Rows), sudoku(Rows), maplist(portray_clause, Rows).
[9, 8, 7, 6, 5, 4, 3, 2, 1].
[2, 4, 6, 1, 7, 3, 9, 8, 5].
[3, 5, 1, 9, 2, 8, 7, 4, 6].
[1, 2, 8, 5, 3, 7, 6, 9, 4].
[6, 3, 4, 8, 9, 2, 1, 5, 7].
[7, 9, 5, 4, 6, 1, 8, 3, 2].
[5, 1, 9, 2, 8, 6, 4, 7, 3].
[4, 7, 2, 3, 1, 9, 5, 6, 8].
[8, 6, 3, 7, 4, 5, 2, 1, 9].

Лучший решатель судоку!

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

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

Все, кроме двух последних строк, исправить несложно. Нам просто нужна новая переменная N и заменить 9 на N. Большая часть жесткого кода находится в последних двух строках.

Мы не можем давать произвольные имена строкам, поэтому нам нужно разделить сетку, используя строки B_R на группу.

/* Result = first N elements of Src List, Rest is Suffix. */
take_firstN(0, Src, [], Src) :- !.
take_firstN(N, [H|T], [H|P], Suffix) :- 
    N #> 0, M #= N-1,
    take_firstN(M, T, P, Suffix).

/* Partitions our matrix into groups with N rows per group */
part(_, [], []) :- !.
part(N, Rows, [Group | RestGroups]) :-
    take_firstN(N, Rows, Group, RowsLeft),
    part(N, RowsLeft, RestGroups).

• Мы создали отношение, которое разбивает список на первые X элементов и остальное. Элементы списка не имеют значения — имеет значение только их порядок. Тот факт, что каждый элемент сам по себе является строкой, не имеет значения для отношения take_firstN().
• Затем мы используем это вспомогательное отношение для записи part(), которая создает разделы строк B_R в каждом разделе — учитывая всю сетку.

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

/* Take first N elements of each of M lists into M lists. RestOf contains suffix of each of those lists (2D) */
take_firstN_fromEach(_, [], [], []) :- !.
take_firstN_fromEach(N, [H|T], [Result|RestOfResults], [RestOfH|RestOfT]) :-
    take_firstN(N, H, Result, RestOfH), /* Take N from first list */
    take_firstN_fromEach(N, T, RestOfResults, RestOfT). /* Take N from other lists */
valid_blocks(_, [X|_]) :- 
    X = [], !.
    valid_blocks(B_C, Partition) :-
    take_firstN_fromEach(B_C, Partition, Grid, OtherGrids),
    flatten(Grid, FlatGrid),
    all_distinct(FlatGrid),
    valid_blocks(B_C, OtherGrids).

• take_firstN_fromEach берет раздел, извлекает элементы B_C из каждой строки, а затем гарантирует, что все эти элементы B_C*B_R различны. Сладкий!

Все, что осталось, это собрать воедино нашу связь судоку. Очень похоже на оригинал!

/* Generalized Sudoku Solver
N - size of entire block of N x N
B_R - mini-block column size
B_C - mini-block column size
*/
gen_sudoku(Rows,N,B_R,B_C):-
    N #>1, B_R #> 1, B_C #> 1, N #= B_R * B_C,
    length(Rows, N), maplist(same_length(Rows), Rows),
    append(Rows, Vs), Vs ins 1..N,
    maplist(all_distinct, Rows),
    transpose(Rows, Columns),
    maplist(all_distinct, Columns),
    part(B_R, Rows, Partitions),
    maplist(valid_blocks(B_C), Partitions).

Теперь мы можем прийти к решению задачи 1 с помощью `problem(1, Rows), gen_sudoku(Rows, 9, 3, 3), maplist(portray_clause, Rows). Лучше всего то, что он работает с разными размерами!

Вывод

Следующая часть задания была еще более сложной. Постановка задачи была такой: при заданной нижней границе X и верхней границе Y можно ли заполнить сетку N*N размерами блоков B_R*B_C так, чтобы сетка имела только единственное решение? Вы можете сделать это быстро? Можете ли вы сделать это с минимальным количеством используемых спотов?

Излишне говорить, что это заняло некоторое время….

Мое решение можно посмотреть здесь: https://github.com/Psyf/Sudoku/blob/main/sudokuB.pl. Решение выполняется за разумное время с использованием алгоритма, основанного на эвристике — вероятность нахождения уникальной сетки при первом запуске уменьшается с увеличением сложности. Отдельное спасибо моему другу Paras за мозговой штурм со мной.

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

Я хотел бы услышать от вас! Как бы вы написали обобщенный решатель судоку на своем любимом языке программирования?