I am trying to write a crossword solver I have got this code but I can't Understand some parts of it:
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 for solving crosswords like this:
What are symbols ;
->
used for?
My main problem is understanding the rules , transpose and more_empty. Any explanation to help me understand the code would be appreciated.
->
and ;
are Prolog's control flow, like the if-then-else satement 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
That should give you some idea what it does. I suggest you translate the more_empty
function into psuedocode yourself (or just step through it in your head), and try to work it out from there.
In addition to the correct answers of Josh and Avi Tshuva stating that a -> b ; c
is like "if a then b else c", I would like to explain that ->
and ;
are individual operators which can be used separately.
;
is logical disjunction, ie. logical "or". So x; y
means "x or y". This makes the conditional statement a bit confusing because a -> b ; c
reads like "a implies b or c" which is obviously not what it means! Even if you parenthesize it like "(a implies b) or c" you get a different meaning from the conditional statement because in this incorrect interpretation, c will always be tried, even if (a implies b) succeeds.
The difference is because ->
has some "non-logical" semantics. From SWI-Prolog docs:
:Condition -> :Action
If-then and If-Then-Else. The->/2
construct commits to the choices made at its left-hand side, destroying choice points created inside the clause (by;/2
), or by goals called by this clause. Unlike!/0
, the choice point of the predicate as a whole (due to multiple clauses) is not destroyed. The combination;/2
and->/2
acts as if defined as:If -> Then; _Else :- If, !, Then. If -> _Then; Else :- !, Else. If -> Then :- If, !, Then.
Please note that(If -> Then)
acts as(If -> Then ; fail)
, making the construct fail 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!
These are Prolog's if-then-else control structure.
The syntax is as follows:
condition -> then statements/decelerations ; else statements/declerations
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With