patient-exit.pl

% A1 A2 A3 A4
% B1 B2 B3 B4
% C1 C2 C3 C4
% D1 D2 D3 D4
%
% Patient is at D1
% Exit is at A4
%
% Patient is about to be discharged but wants to visit every other patient
% before leaving. Visiting the same patient twice would make him sick.

goal((a,4)).
init((d,1)).

move((Col,Row), (Col,NewRow)) :- move_row(Row, NewRow).
move((Col,Row), (NewCol,Row)) :- move_col(Col, NewCol).

move_row(1,2). move_row(2,3). move_row(3,4).
move_row(2,1). move_row(3,2). move_row(4,3).

move_col(a,b). move_col(b,c). move_col(c,d).
move_col(b,a). move_col(c,b). move_col(d,c).

solve0(State, Moves, Moves) :-
  goal(State),
  length(Moves,Len),
  Len >= 15.
solve0(State, History, Moves) :-
  move(State, NewState),
  \+member(NewState, History),
  solve0(NewState, [NewState|History], Moves).

solve(Moves) :-
  init(State),
  solve0(State, [], RevMoves),
  reverse(RevMoves, Moves).

?- solve(Moves), writeln(Moves).