Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How this prolog crossword solver works?

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:

enter image description here

enter image description here

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.

like image 840
Freelancer Avatar asked Sep 30 '22 03:09

Freelancer


3 Answers

-> 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.

like image 159
Zaz Avatar answered Oct 20 '22 16:10

Zaz


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!

like image 1
Hugh Allen Avatar answered Oct 20 '22 16:10

Hugh Allen


These are Prolog's if-then-else control structure.

The syntax is as follows:

condition -> then statements/decelerations ; else statements/declerations

like image 1
Avi Tshuva Avatar answered Oct 20 '22 17:10

Avi Tshuva