Successful prolog query not showing true

Question

Testing some Prolog code to see if I can show gameover when a white(w) has a connected path from one side of the board to the other. My biggest problem so far is while gameover/2 does go through all the nodes on each side and checks if their connected it doesn't stop or show when they are. Thus when testing this query:

gameover([[e,e,b,e,e],[e,w,w,b,e],[b,w,b,w,w],[w,w,b,b,b],[e,e,b,w,e]], w).

Prolog returns no when it should be true. I've gone through everything I can but I am new to Prolog and I'm sure I must be missing something obvious.

gameover(State, w) :-
    width(State, W), write(W), nl,
    series(1, W, NewList), write(NewList), nl,
    member(X1, NewList), write(X1), nl,
    write(loc(X1,1)), nl, write('X1'), nl,
    member(X2, NewList), write(X2), nl,
    write(loc(X2,W)), nl, write('X2'), nl,
    connected(State, loc(X1,1), loc(X2,W), w).

I've tested connected, member, series and width each very thoroughly and am sure they all work so I think it must be something I have done in the code above. There is also a similar predicate for gameover(State,b) that uses the Y coordinate rather than the X. It's also having the same troubles.

Connected:

connected(State, Start, End, Colour) :- get_location(State, End, Colour),
                                        get_location(State, Start, Colour),
                                        connects(State, End, Colour, Start, [Start]).

connected(_State, _Next, _Colour, End, Close):- member(End, Close).

%checking to make sure every node is connected to the other using linked
%list of children from linked- check child is not member of closed list(meaning it has been checked before)
%get location of child to check for colour
%recursive call, include children in closed list to mark they have been checked and won't be checked again                                      
connects(State, End, Colour, Next, Close) :-  linked(Next, Child),
                                                \+member(Child, Close),
                                                get_location(State, Child, Colour),
                                                connects(State, End, Colour, Child, [Child|Close]).

connects(_State, End, _Colour, End, _Close).

It's Hex. connected determines if two grid locations are connected by an unbroken path of a specific colour. en.wikipedia.org/wiki/Hex_(board_game) — user3738728

CapelliC CapelliC · Accepted Answer · 2014-06-15T11:30:41

with appropriate simplification, and removing undue display of intermediate computation, here is a sketch that could help you

gameover(State, Colour) :-
    width(State, W),
    get_location(State, loc(X1,1), Colour),
    connected(State, loc(X1,1), loc(_,W), w).

connected(State, L1, L2, Colour) :-
    connected_(State, [L1], L2, Colour).

connected_(_State, [Target|_], Target, _Colour).
connected_(State, [Last|Visited], Target, Colour) :-
    linked(Last,Link),
    get_location(State, Link, Colour),
    \+ memberchk(Link, Visited),
    connected_(State, [Link,Last|Visited], Target, Colour).

the key it's the service predicate connected_, that holds a list of visited locs instead of the starting one, then enabling a simple depth first visit. A small test, with a silly topology

width(_State, 3).

linked(loc(X,Y),loc(U,V)) :- (U is X+1 ; U is X-1), Y=V.
linked(loc(X,Y),loc(U,V)) :- (V is Y+1 ; V is Y-1), X=U.

get_location(State, loc(X,Y), Colour) :-
    nth(Y,State,Row), nth(X,Row,Colour).

?- S = [[e,w,e],[e,w,e],[e,w,e]], gameover(S,w).
S = [[e, w, e], [e, w, e], [e, w, e]] 
.

?- S = [[w,e,e],[e,w,e],[e,w,e]], gameover(S,w).
false.

Successful prolog query not showing true

1 Answers