Why is this prolog function running indefinitely, how do I fix it?

Question

I am trying to create a prolog predicate to solve this zebra problem however It keeps on running indefinitely and does not produce a result, how can I fix this.

Here is the Zebra Problem:

The five biggest DJs in the world are going to play in an electronic music festival, each one in a specific stage. They are side by side waiting to play. Find out their nationalities,vhobbies and which genre they play.

DJ Properties:

• Shirt colors: black, blue, green, red, white

• Nationalities: American, Canadian, Dutch, French, Scottish

• Music genres: drum and bass, dubstep, EDM, house, trance

• Performance stages: Arcadia, Asgard, Shangri-la, Valhalla, Xibalba

• Ages: 25, 30, 35, 40, 45

• Hobbies: camping, juggling, painting, singing, surfing

Clues

• The Scott is somewhere to the left of the DJ wearing the White shirt.

• At the fourth position is the DJ who is going to play on the Arcadia stage.

• The 30-year-old DJ is at the first position.

• The DJ that plays EDM is exactly to the right of the Canadian.

• The one who likes Painting is next to the DJ who plays Dubstep.

• The DJ wearing the Black shirt is somewhere between the Scott and the Dubstep player, in that order.

• The French DJ is next to the one wearing the Blue shirt.

• At one of the ends is the DJ that likes Camping.

• The DJ who is going to play on the Asgard stage is wearing the Blue shirt.

• The one that likes Painting is somewhere between the DJ wearing Green and the DJ wearing Blue, in that order.

• At the fifth position is the DJ who plays Drum and bass.

• In the middle is the DJ who is going to play on the Asgard stage.

• The one who plays Trance is next to the one who plays Dubstep.

• The Canadian is exactly to the left of the DJ who likes Juggling

• The DJ whose hobby is Singing is exactly to the right of the DJ wearing the Black shirt.

• The DJ in his Mid-thirties is next to the DJ who is into Juggling.

• The 40-year-old DJ is at the fourth position.

• The 40-year-old DJ is somewhere between the Dutch and the youngest DJ, in that order.

• The DJ wearing Blue is somewhere to the left of the DJ who is going to play on the Xibalba stage.

• The one who enjoys Surfing is going to play on the Valhalla stage.

• The DJ wearing the Red shirt is somewhere to the right of the French

Here is my code so far:

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

left_of(A, B, L) :- append(_, [A|T], L), member(B, T).

next_to(A, B, L) :- left_of(A, B, L) ; left_of(B, A, L).

solve(DJs) :-
    DJs = [_, _, _, _, _],

    % Clue 1
    member([scott, _, _, _, _, _], DJs),
    member([_, white, _, _, _, _], DJs),
    left_of([scott, _, _, _, _, _], [_, white, _, _, _, _], DJs),

    % Clue 2
    DJs = [_, _, _, [_, _, _, arcadia, _, _], _],

    % Clue 3
    DJs = [[_, _, _, _, 30, _], _, _, _, _],

    % Clue 4
    member([canadian, _, _, _, _, _], DJs),
    member([_, _, edm, _, _, _], DJs),
    left_of([canadian, _, _, _, _, _], [_, _, edm, _, _, _], DJs),

    % Clue 5
    next_to([_, _, _, _, _, painting], [_, _, dubstep, _, _, _], DJs),

    % Clue 6
    left_of([scott, _, _, _, _, _], [_, black, _, _, _, _], DJs),
    left_of([_, black, _, _, _, _], [_, _, dubstep, _, _, _], DJs),

    % Clue 7
    next_to([french, _, _, _, _, _], [_, blue, _, _, _, _], DJs),

    % Clue 8
    (DJs = [[_, _, _, _, _, camping], _, _, _, _] ; DJs = [_, _, _, _, [_, _, _, _, _, camping]]),

    % Clue 9
    member([_, blue, _, asgard, _, _], DJs),

    % Clue 10
    left_of([_, green, _, _, _, _], [_, _, _, _, _, painting], DJs),
    left_of([_, _, _, _, _, painting], [_, blue, _, _, _, _], DJs),

    % Clue 11
    DJs = [_, _, _, [_, _, _, _, 40, _], _],

    % Clue 12
    next_to([_, _, trance, _, _, _], [_, _, dubstep, _, _, _], DJs),

    % Clue 13
    left_of([canadian, _, _, _, _, _], [_, _, _, _, _, juggling], DJs),

    % Clue 14
    left_of([_, black, _, _, _, _], [_, _, _, _, _, singing], DJs),

    % Clue 15
    next_to([_, _, _, _, 35, _], [_, _, _, _, _, juggling], DJs),

    % Clue 16
    left_of([dutch, _, _, _, _, _], [_, _, _, _, 25, _], DJs),
    left_of([_, _, _, _, 25, _], [_, _, _, _, 40, _], DJs),

    % Clue 17
    left_of([_, blue, _, _, _, _], [_, _, _, xibalba, _, _], DJs),

    % Clue 18
    member([_, _, _, valhalla, _, surfing],DJs),

    % Clue 19
    member([_, red, _, _, _, _], DJs),
    left_of([french, _, _, _, _, _], [_, red, _, _, _, _], DJs),

    % Check properties
    member([american, _, _, _, _, _], DJs),
    member([canadian, _, _, _, _, _], DJs),
    member([dutch, _, _, _, _, _], DJs),
    member([french, _, _, _, _, _], DJs),
    member([scottish, _, _, _, _, _], DJs),

    member([_, black, _, _, _, _], DJs),
    member([_, blue, _, _, _, _], DJs),
    member([_, green, _, _, _, _], DJs),
    member([_, red, _, _, _, _], DJs),
    member([_, white, _, _, _, _], DJs),

    member([_, _, drum_and_bass, _, _, _], DJs),
    member([_, _, dubstep, _, _, _], DJs),
    member([_, _, edm, _, _, _], DJs),
    member([_, _, house, _, _, _], DJs),
    member([_, _, trance, _, _, _], DJs),

    member([_, _, _, arcadia, _, _], DJs),
    member([_, _, _, asgard, _, _], DJs),
    member([_, _, _, shangri_la, _, _], DJs),
    member([_, _, _, valhalla, _, _], DJs),
    member([_, _, _, xibalba, _, _], DJs),

    member([_, _, _, _, 25, _], DJs),
    member([_, _, _, _, 30, _], DJs),
    member([_, _, _, _, 35, _], DJs),
    member([_, _, _, _, 40, _], DJs),
    member([_, _, _, _, 45, _], DJs),

    member([_, _, _, _, _, camping], DJs),
    member([_, _, _, _, _, juggling], DJs),
    member([_, _, _, _, _, painting], DJs),
    member([_, _, _, _, _, singing], DJs),
    member([_, _, _, _, _, surfing], DJs).

Answer 1

Try to put your code into small manageable parts first. And then, use the prolog-toplevel to see if the answers you get are the answers you want. Just your first clue is:

clue1(DJs) :-
    DJs = [_, _, _, _, _],
    % Clue 1
    member([scott, _, _, _, _, _], DJs),
    member([_, white, _, _, _, _], DJs),
    left_of([scott, _, _, _, _, _], [_, white, _, _, _, _], DJs).

?- clue1(DJs).
   DJs = [[scott,white,_A,_B,_C,_D],[_E,white,_F,_G,_H,_I],_J,_K,_L], unexpected
;  DJs = [[scott,white,_A,_B,_C,_D],_E,[_F,white,_G,_H,_I,_J],_K,_L], unexpected
;  ... % many answers omitted
;  DJs = [[_A,white,_B,_C,_D,_E],[scott,_F,_G,_H,_I,_J],[_K,white,_L,_M,_N,_O],_P,_Q], unexpected
;  ... % many answers omitted
;  false.

In total, just for the first clue, there are 250 answers. Many of which can never lead to a solution: The first two answers have two white instead of just one. The last shown answer has scott to the right (and not left) of a white. It is quite similar with the subsequent clues. Let's remove the two member/2 goals since they are already implied by left_of/2. As a result we narrowed down the problem to 10 answers.

?- clue1(DJs).
   DJs = [[scott,_A,_B,_C,_D,_E],[_F,white,_G,_H,_I,_J],_K,_L,_M]
;  DJs = [[scott,_A,_B,_C,_D,_E],_F,[_G,white,_H,_I,_J,_K],_L,_M]
;  DJs = [[scott,_A,_B,_C,_D,_E],_F,_G,[_H,white,_I,_J,_K,_L],_M]
;  DJs = [[scott,_A,_B,_C,_D,_E],_F,_G,_H,[_I,white,_J,_K,_L,_M]]
;  DJs = [_A,[scott,_B,_C,_D,_E,_F],[_G,white,_H,_I,_J,_K],_L,_M]
;  DJs = [_A,[scott,_B,_C,_D,_E,_F],_G,[_H,white,_I,_J,_K,_L],_M]
;  DJs = [_A,[scott,_B,_C,_D,_E,_F],_G,_H,[_I,white,_J,_K,_L,_M]]
;  DJs = [_A,_B,[scott,_C,_D,_E,_F,_G],[_H,white,_I,_J,_K,_L],_M]
;  DJs = [_A,_B,[scott,_C,_D,_E,_F,_G],_H,[_I,white,_J,_K,_L,_M]]
;  DJs = [_A,_B,_C,[scott,_D,_E,_F,_G,_H],[_I,white,_J,_K,_L,_M]]
;  false.

Now, you can observe the failure with some patience. To improve speed you could move up clues, that consist of a single unification like, clue 2, 3, and 11. Also you could ensure with the help of dif/2 that all corresponding entries are different. This would improve speed, but still there would be failure.

Here is a generalization of your program that still fails. I have removed many of the goals in it, leaving only:

solve(DJs) :-
    DJs = [_, _, _, _, _],
    left_of([scott, _, _, _, _, _], [_, white, _, _, _, _], DJs),
    member([american, _, _, _, _, _], DJs),
    member([canadian, _, _, _, _, _], DJs),
    member([dutch, _, _, _, _, _], DJs),
    member([french, _, _, _, _, _], DJs),
    member([scottish, _, _, _, _, _], DJs).

?- solvex(DJs).
   false, unexpected.

Because this fragment fails, also your original program will fail. By fixing this problem, your program works. So you should be able to figure that out. Finally, your problem has, however, 48 solutions which is a bit unusual for a zebra puzzle which typically has only a single solution.