Skip to content

Instantly share code, notes, and snippets.

@afvanwoudenberg
Last active March 25, 2023 13:56
Show Gist options
  • Save afvanwoudenberg/e7107f7b2b1e9e5a59f231ccdafd4ab1 to your computer and use it in GitHub Desktop.
Save afvanwoudenberg/e7107f7b2b1e9e5a59f231ccdafd4ab1 to your computer and use it in GitHub Desktop.
A Prolog solver for the bridge and torch puzzle
% A Prolog solver for the bridge and torch puzzle
% https://en.wikipedia.org/wiki/Bridge_and_torch_problem
print_all_solutions :-
findall(_,print_solution,_).
print_solution :-
init(State),
solve(State,Solution,EndState),
writeln('Start state:'),
writeln(State),
writeln('Solution:'),
writeln(Solution),
writeln('Final state:'),
writeln(EndState), nl.
solve(State,[],State) :- goal(State).
solve(State,[Move|Tail],EndState) :- s(State,Move,NewState), solve(NewState,Tail,EndState).
goal(state([],right,[_,_,_,_],T)) :- T =< 17.
init(state([a,b,c,d],left,[],0)).
s(state(L1,left,L2,T),cross(L3),state(L4,right,L6,T2)) :-
select_one_or_two(L1,L3,L4),
ord_union(L2,L3,L6),
min_time_needed(L3,Tn),
T2 is T + Tn,
T2 =< 17.
s(state(L1,right,L2,T),cross(L3),state(L4,left,L5,T2)) :-
select_one_or_two(L2,L3,L5),
ord_union(L1,L3,L4),
min_time_needed(L3,Tn),
T2 is T + Tn,
T2 =< 17.
select_one_or_two(L,[Sel],L2) :- select(Sel,L,L2).
select_one_or_two(L,[Sel1,Sel2],L2) :- select(Sel1,L,NewL), select(Sel2,NewL,L2), Sel1@<Sel2.
min_time_needed([A],T) :- time_needed(A,T).
min_time_needed([A,B],T) :- time_needed(A,T1), time_needed(B,T2), max_list([T1,T2],T).
time_needed(a,1).
time_needed(b,2).
time_needed(c,5).
time_needed(d,10).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment