How does this crossword puzzle prologue work?

Question

I'm trying to write a crossword puzzle, I have this code, but I can not understand some of its parts:

size(5). black(1,3). black(2,3). black(3,2). black(4,3). black(5,1). black(5,5). words([do,ore,ma,lis,ur,as,po, so,pirus, oker,al,adam, ik]) . :- use_module(library(lists),[nth1/3, select/3]). crossword(Puzzle) :- words(WordList), word2chars(WordList,CharsList), make_empty_words(EmptyWords) , fill_in(CharsList,EmptyWords), word2chars(Puzzle,EmptyWords). word2chars([],[]). word2chars([Word|RestWords] ,[Chars|RestChars] ) :- atom_chars(Word,Chars), word2chars(RestWords,RestChars). fill_in([],[]). fill_in([Word|RestWords],Puzzle) :- select(Word,Puzzle,RestPuzzle), fill_in(RestWords,RestPuzzle). make_empty_words(EmptyWords) :- size(Size), make_puzzle(Size,Puzzle), findall(black(I,J),black(I,J),Blacks) , fillblacks(Blacks,Puzzle), empty_words(Puzzle,EmptyWords). make_puzzle(Size,Puzzle) :- length(Puzzle,Size), make_lines(Puzzle,Size). make_lines([],_). make_lines([L|Ls],Size) :- length(L,Size), make_lines(Ls,Size). fillblacks([],_). fillblacks([black(I,J)|Blacks],Puzzle) :- nth1(I,Puzzle,LineI), nth1(J,LineI,black), fillblacks(Blacks,Puzzle). empty_words(Puzzle,EmptyWords) :- empty_words(Puzzle,EmptyWords,TailEmptyWords), size(Size), transpose(Size,Puzzle,[],TransposedPuzzle), empty_words(TransposedPuzzle,TailEmptyWords,[] ). empty_words([],Es,Es). empty_words([L|Ls],Es,EsTail) :- empty_words_on_one_line(L,Es,Es1) , empty_words(Ls,Es1,EsTail). empty_words_on_one_line([], Tail, Tail). empty_words_on_one_line([V1,V2|L],[[V1,V2|Vars]|R],Tail) :- var(V1), var(V2), !, more_empty(L,RestL,Vars), empty_words_on_one_line(RestL,R,Tail) . empty_words_on_one_line([_| RestL],R, Tail) :- empty_words_on_one_line(RestL,R,Tail) . more_empty([],[],[]). more_empty([V|R],RestL,Vars) :- ( var(V) -> Vars = [V|RestVars], more_empty(R,RestL,RestVars) ; RestL = R, Vars = [] ). transpose(N,Puzzle,Acc,TransposedPuzzle) :- ( N == 0 -> TransposedPuzzle = Acc ; nth_elements(N,Puzzle,OneVert), M is N - 1, transpose(M,Puzzle,[OneVert|Acc], TransposedPuzzle) ). nth_elements(_,[],[]). nth_elements(N,[X|R],[NthX| S]) :- nth1(N,X,NthX), nth_elements(N,R,S). 

This code is used to solve crosswords as follows:

What characters ; -> are used for?

My main problem is understanding the rules, transpose and more_empty . Any explanations that help me understand the code would be appreciated.

Answer 1

In addition to the correct answers of Josh and Avi Tshuva that a -> b ; c a -> b ; c as "if a then b else c", I would like to explain that -> and ; are separate operators that can be used individually.

; is a logical disjunction, i.e. logical "or". So x; y x; y means "x or y". This makes the conditional statement somewhat confusing because a -> b ; c a -> b ; c reads as "a implies b or c", which is clearly not what it means! Even if you copy it as "(a implies b) or c", you get a different value from the conditional operator, because in this incorrect interpretation c will always be checked, even if (a implies b) is successful.

The difference is that -> has some "illogical" semantics. From SWI-Prolog Docs :

: Condition →: Action

If-then and If-Then-Else. The construction ->/2 makes a choice made on its left side, destroying the selection points created inside the sentence (on ;/2 ), or goals called this sentence. Unlike !/0 , the predicate selection point as a whole (due to multiple sentences) is not destroyed. The combination ;/2 and ->/2 acts as if it were defined as:
If -> Then; _Else :- If, !, Then. If -> _Then; Else :- !, Else. If -> Then :- If, !, Then.
Note that (If -> Then) acts like (If -> Then ; fail) , making the fail construct if the condition fails. This unusual semantics is part of the ISO and all de facto Prolog standards.

(note that in the above quote, If , Then , etc. are variables!)

So beware of anything with an implicit cut !

Answer 2

-> and ; - Prolog control flow, for example, if - , and then - else in other languages. So:

 transpose(N,Puzzle,Acc,TransposedPuzzle) :- ( N == 0 -> TransposedPuzzle = Acc ; nth_elements(N,Puzzle,OneVert), M is N - 1, transpose(M,Puzzle,[OneVert|Acc], TransposedPuzzle) ). 

translates to psuedocode:

 def transpose(N, Puzzle, Acc) if N == 0 return Acc else OneVert = nth_elements(N, Puzzle) transpose(N-1, Puzzle, [OneVert, Acc]) 

or

 def transpose(N, Puzzle, Acc) while N > 0 OneVert = nth_elements(N, Puzzle) Acc = [OneVert, Acc] N = N - 1 return Acc 

This should give you an idea of ​​what he is doing. I suggest you translate the more_empty function into psuedocode yourself (or just skip it in your head), and try to work it out there.

Answer 3

This is the Prolog if-then-else control structure.

The syntax is as follows:

condition → then approval / deceleration; more statements / declerations