Пролог: Изучение на примере

Question

Я пытаюсь немного узнать о swi-prolog (помимо основных, бесполезных программ).

Может ли кто-нибудь объяснить (возможно, в псевдокоде), что делает этот решатель sudoku и связанные с ним функции? Если вам нужна дополнительная ссылка, она находится в пакете swip-пролога CLP (FD).

Спасибо!

:- use_module(library(clpfd)). 
sudoku(Rows) :-             
     length(Rows, 9), maplist(length_(9), Rows),     
     append(Rows, Vs), Vs ins 1..9,        
     maplist(all_distinct, Rows),        
     transpose(Rows, Columns), maplist(all_distinct, Columns), 
     Rows = [A,B,C,D,E,F,G,H,I],         
     blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).   


length_(L, Ls) :- length(Ls, L).         

blocks([], [], []).             
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
     all_distinct([A,B,C,D,E,F,G,H,I]),       
     blocks(Bs1, Bs2, Bs3).          


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

Answer 1

судоку/1 в основном описывает ограничения решение Sudoku должны удовлетворять, где доска представлена ​​в виде списка из девяти списков длиной девять. проблема/2 присваивает частично запрограммированную доску номер проблемы. Чтобы использовать его, вы должны сделать

? - проблема (1, доска), судоку (доска).

Вы должны прочитать предикаты, используемые в the documentation.

Answer 2

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

Прежде всего A :- B, C, D означает А истинно (успешно), если B И C И D являются истинными.

фрагмент кода вы публикуемую проверяет правильность головоломки судоку, есть три условия:

• элементы различны по строкам
• элементы различны по столбцам
• элементы являются все разные блоки 3x3

Как это работает?

судоку (Ряды) верно, если:

1. length(Rows, 9) -> есть 9 элементов в строках
2. maplist(_length(9), Rows) ->maplist проверяет предикат (первый параметр) по каждому элементу списка (второй параметр). Это означает, что каждая строка должна иметь длину 9.
3. -> то же, что и раньше, но мы проверяем, имеют ли каждая строка отдельные (не равные попарные) элементы.
4. transpose(Rows, Columns), maplist(all_distinct, Columns) -> перенесет строку в столбцы, чтобы проверить, если все они различны и, выбирая их в вертикальном пути
5. Rows = [A,B,C,D,E,F,G,H,I] -> разбивает список строк и поместить каждый в другой переменной A, B, C, D ... так что A будет первым рядом, B вторым и так далее
6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) -> этот предикат должен быть правдой для триплетов строк.

Давайте поговорим о части blocks, что довольно забавно для понимания. Мы хотим проверить, что каждый блок 3x3 содержит различные значения. Как мы можем сделать это?

Предположим, что для трех рядов условие должно быть истинным для первых трех элементов каждой строки (первый блок 3x3), для элементов с 4-го по 6-й (второй блок) и 7-го-9-го (третий блок).

Итак, мы можем думать рекурсивно: blocks([],[],[]) тривиально верно, у нас есть пустые списки.

Корпус blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) выбран при вызове предиката blocks с параметрами, которые перечислены с элементами AT LEAST 3. Таким образом, мы можем проверить, все ли разные A, B, C, D, E, F, G, H, I, тогда мы вызываем blocks, рекурсивно используем в качестве параметров списки остатков (без первых трех элементов). Это то, о чем пролог!

blocks Итак, blocks будет называться первым с тремя строками из 9 элементов, он будет проверять, что первые 3 из каждой строки различны, и называет себя тремя списками из 6 элементов, снова проверит их и вызовет 3 списка из 3 элементов , проверьте его снова и назовите себя тремя пустыми списками (треугольный случай, который всегда выполняется).

Answer 3

о "дописать (Ряды, Vs), Vs аудиовходов 1..9"

http://www.swi-prolog.org/pldoc/man?predicate=append%2F2

Это означает, что все элементы списка списков должны находиться в домене 1..9.