Skip to content

Instantly share code, notes, and snippets.

@afvanwoudenberg
Last active March 29, 2023 17:14
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save afvanwoudenberg/06b7b3d115faa95a4332e32e5eb2988f to your computer and use it in GitHub Desktop.
Prolog code to solve the icosian game
% A Prolog solver for the Icosian game
% https://en.wikipedia.org/wiki/Icosian_game
icosian_puzzle_edges([
(b,c), (b,g), (b,z), (c,d), (c,p), (d,f), (d,m), (f,g), (f,k), (g,h),
(h,j), (h,x), (j,k), (j,v), (k,l), (l,t), (l,m), (m,n), (n,p), (n,s),
(p,q), (q,z), (q,r), (r,s), (r,w), (s,t), (t,v), (v,w), (w,x), (x,z)
]).
connected(Adj,P,Q) :- member((P,Q),Adj); member((Q,P),Adj).
graph_order(Adj,N) :-
findall(A,connected(Adj,A,_),B0),
sort(B0,B),
length(B,N).
hamiltonian_cycle(Adj,[Start|TourRest]) :-
graph_order(Adj,N),
append([[Start],MidTour,[Start]],[Start|TourRest]),
length([Start|MidTour],N),
hamiltonian_cycle(Adj,Start,MidTour,[Start]).
hamiltonian_cycle(Adj,Start,[],[LastVisited|_]) :-
connected(Adj,LastVisited,Start).
hamiltonian_cycle(Adj,Start,[Head|Tail],[VisitedHead|VisitedTail]) :-
connected(Adj,VisitedHead,Head),
not(member(Head,[VisitedHead|VisitedTail])),
hamiltonian_cycle(Adj,Start,Tail,[Head,VisitedHead|VisitedTail]).
print_icosian_puzzle :- print_icosian_solution([]).
edge_in_tour(P,Q,Tour) :-
append([_,[P,Q],_],Tour);
append([_,[Q,P],_],Tour).
format_edge(P,Q,Tour,Atom,Out) :-
edge_in_tour(P,Q,Tour),
format(atom(Out),'\e[31m~w\e[0m',[Atom]), !.
format_edge(_P,_Q,_Tour,Atom,Atom).
print_icosian_solution(Tour) :-
findall(F,(member((P,Q,A),[
(b,c,'-'), (b,g,'/'), (b,z,'\\'), (c,d,'\\'), (c,p,'/'),
(d,f,'/'), (d,m,'\\'), (f,g,'\\'), (f,k,'|'), (g,h,'/'),
(h,j,'\\'), (h,x,'\\'), (j,k,'/'), (j,v,'/'), (k,l,'\\'),
(l,t,'\\'), (l,m,'/'), (m,n,'/'), (n,p,'\\'), (n,s,'---'),
(p,q,'\\'), (q,z,'/'), (q,r,'|'), (r,s,'\\'), (r,w,'/'),
(s,t,'/'), (t,v,'-------'), (v,w,'\\'), (w,x,'---'), (x,z,'/')
]),format_edge(P,Q,Tour,A,F)),[BC,BG,BZ,CD,CP,DF,DM,FG,FK,GH,
HJ,HX,JK,JV,KL,LT,LM,MN,NP,NS,PQ,QZ,QR,RS,RW,ST,TV,VW,WX,XZ]),
format(' R',[]), nl,
format(' ~w~w~w',[RW,QR,RS]), nl,
format(' ~w ~w ~w',[RW,QR,RS]), nl,
format(' ~w ~w ~w',[RW,QR,RS]), nl,
format(' ~w Q ~w',[RW,RS]), nl,
format(' ~w ~w ~w ~w',[RW,QZ,PQ,RS]), nl,
format(' ~w ~w ~w ~w',[RW,QZ,PQ,RS]), nl,
format(' ~w Z P ~w',[RW,RS]), nl,
format(' ~w ~w ~w ~w ~w ~w',[RW,XZ,BZ,CP,NP,RS]), nl,
format(' ~w ~w B~wC ~w ~w',[RW,XZ,BC,NP,RS]), nl,
format(' ~w ~w ~w ~w ~w ~w',[RW,XZ,BG,CD,NP,RS]), nl,
format(' ~w ~w G D ~w ~w',[RW,XZ,NP,RS]), nl,
format('W~wX ~w ~w ~w ~w N~wS',[WX,GH,FG,DF,DM,NS]), nl,
format(' ~w ~w ~w ~w ~w ~w ~w ~w',[VW,HX,GH,FG,DF,DM,MN,ST]), nl,
format(' ~w H F M ~w',[VW,ST]), nl,
format(' ~w ~w ~w ~w ~w',[VW,HJ,FK,LM,ST]), nl,
format(' ~w ~w K ~w ~w',[VW,HJ,LM,ST]), nl,
format(' ~w ~w ~w ~w ~w ~w',[VW,HJ,JK,KL,LM,ST]), nl,
format(' ~w J L ~w',[VW,ST]), nl,
format(' ~w ~w ~w ~w',[VW,JV,LT,ST]), nl,
format(' V~wT',[TV]), nl.
solve_icosian_puzzle :-
icosian_puzzle_edges(Adj),
hamiltonian_cycle(Adj,Tour),
print_icosian_solution(Tour).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment