fixedpoint.jp - The right answer of "The Shipman's Puzzle" from "The Canterbury Puzzles"




The right answer of "The Shipman's Puzzle" from "The Canterbury Puzzles"

The Canterbury Puzzles and Other Curious Problems is a great heritage for those who love fascinating brain teasers. These days its whole text is freely available thanks to the Project Gutenberg.

Here we show that the answer described in the book for its 18th puzzle called "Shipman's Puzzle", i.e. 264, is wrong, and provide the right answer: 528. The original publication dated to 1907, so this seems to correct a 111-year-old misinformation.

The following Prolog program defines predicate complete_voyage/1 which generates all the possible complete voyages. We have confirmed it works with SWI-Prolog Version 7.2.3.

shipmans.pl
island(a). % "a" represents the initial island
island(b).
island(c).
island(d).
island(e).

edge(I,J) :- island(I),island(J),I\=J.

course(I-J) :- edge(I,J),sort([I,J],[I,J]).

count_course(N) :- findall(C,course(C),Cs),length(Cs,N).

taken(I,J,X) :- member(I-J,X);member(J-I,X).

voyage(I,[],[I-a]) :- edge(I,a).
voyage(I,[I1-I2|X],[I-I1,I1-I2|X]) :- edge(I,I1),edge(I1,I2),voyage(I1,X,[I1-I2|X]),\+taken(I,I1,[I1-I2|X]).

complete_voyage(X) :- count_course(N),length(X,N),voyage(a,_,X).

answer(N) :- setof(X,complete_voyage(X),Xs),length(Xs,N).

compact([],[]).
compact([_-J|X],[J|Y]) :- compact(X,Y).

print_all_complete_voyage :- forall(complete_voyage(V),
                                    (print(a),
                                     compact(V,X),
                                     forall(member(E,X),print(E)),
                                     nl)).

Our speculation of the reason why the author and many others overlooked the mistake is simple; it is well-known that 264 is the number of Eulerian circuits in \(K_5\), the complete graph with five vertices [1], which is a formal representation of the "CHART of ye MAGDALEN". However, when counting Eulerian circuits, a cyclic permuation of the already-counted one is skipped. For example, the circuit "a -> b -> c -> a -> d -> b -> e -> c -> d -> e -> a" and "a -> d -> b -> e -> c -> d -> e -> a -> b -> c -> a" are regarded as equivalent. On the other hand, the puzzle in problem asks the number of different ways to pass along all courses, thus the above two should be counted separately.

[1] B. D. McKay and R. W. Robinson, Asymptotic enumeration of Eulerian circuits in the complete graph, Combin. Prob. Comput., 7 (1998) 437-449.


© 2006-2018 fixedpoint.jp