My Prolog code runs forever

Help!
, , , ,
1

I have a code that suppose to solve a crossword puzzle (find all combinations to the crossword puzzle from given txt file. I got a little help from the chatgpt but couldnt solve my problem. It tooks forever to run and never gives an output. Code is as follows:
:- style_check(-singleton).
Read the words from a file Read the words from a file
read_words(Words) :-
open(‘words.txt’, read, Stream),
read_words(Stream, Words),
close(Stream).

read_words(Stream, [Word | Rest]) :-
+ at_end_of_stream(Stream),
read(Stream, Term),
Term =… [_, Word],
read_words(Stream, Rest).

read_words(_, ).

% Check if two words intersect at a given position
intersect(Word1, Word2, Pos1, Pos2) :-
nth1(Pos1, Word1, Char1),
nth1(Pos2, Word2, Char2),
Char1 = Char2.

% Solve the crossword puzzle
solve_puzzle(WordLengths, Intersections, Words) :-
read_words(AllWords),
find_words(WordLengths, AllWords, Words),
check_intersections(Words, Intersections),
Words = [Word0, Word1, Word2, Word3, Word4],
nth1(2, Word0, LastChar0),
nth1(2, Word1, LastChar1),
LastChar0 = LastChar1,
nth1(4, Word0, SecondChar2),
nth1(2, Word2, SecondChar2),
nth1(3, Word2, LastChar3),
nth1(1, Word4, LastChar3).

Find words of specified lengths find_words([], _, []). find_words([Length | RestLengths], AllWords, [Word | RestWords]) :- member(Word, AllWords), atom_length(Word, Length), Length =< 6, Maximum word length constraint
find_words(RestLengths, AllWords, RestWords),
length(RestWords, NumRestWords),
NumRestWords < 10. % Limit the number of generated words to 10

% Check if words satisfy intersection constraints
check_intersections(, _).
check_intersections([Word | RestWords], Intersections) :-
check_word_intersections(Word, RestWords, Intersections),
check_intersections(RestWords, Intersections).

% Check if a word satisfies intersection constraints with other words
check_word_intersections(_, , _).
check_word_intersections(Word, [Word2 | RestWords], Intersections) :-
member([Pos1, Pos2, Pos3, Pos4], Intersections),
nth1(Pos1, Word, Char1),
nth1(Pos2, Word2, Char2),
nth1(Pos3, Word3, Char3),
nth1(Pos4, Word4, Char4),
Char1 = Char2,
Char1 = Char3,
Char1 = Char4,
check_word_intersections(Word, RestWords, Intersections).

% Entry point predicate
grid(WordLengths, Intersections, Words) :-
solve_puzzle(WordLengths, Intersections, Words).

for example I am trying to run grid([5,3,4,4,3], [[0,1,1,2],[0,3,2,1],[2,3,3,2],[3,3,4,0]], Words). but it doesnt give an output.

2

Usual reminder: You can step through your program, to see exactly what is happening and where it is going wrong, using e.g. trace. - SWI-Prolog -- Manual

1 Like
3

Also, if you enclose your code within triple back-ticks, then it becomes more readable (using “markdown”). I had to make quite a few edits to what you posted to get this:

read_words(Stream, [Word | Rest]) :-
    \+ at_end_of_stream(Stream),
    read(Stream, Term),
    Term =.. [_, Word],
    read_words(Stream, Rest).
read_words(_, []).

and I’d rewrite it this way:

read_words(Stream, []) :-
    at_end_of_stream(Stream),
    !.
read_words(Stream, [Word | Rest]) :-
    read(Stream, Term),
    Term =.. [_, Word],
    read_words(Stream, Rest).

(although the code feels a bit strange … read/2 can handle list of words like [foo, bar, something].

4

That is not steadfast. Can use:

    read_words(Stream, Rest1),
    Rest1 = Rest.

… which allows the potential for JIT indexing on the 2nd arg of read_words/2.

5

Is this better?

read_words(Stream, Words) :-
    (   at_end_of_stream(Stream)
    ->  Words = []
    ;   read(Stream, Term),
        Term =.. [_, Word],
        Words = [Word|Rest],
        read_words(Stream, Rest)
    ).
6

Yeah, it’s steadfast.

My inspiration is: Prolog project issue with GNU Prolog - Stack Overflow

1 Like
7

If you aren’t a super expert, and you want at least to start to understand how prolog works, I would also suggest to use the trace facility. There is also a graphical version which is invoked with ?- gtrace.. Both versions help a lot in understanding where prolog actually does something which is different from what you had in mind