/* Zoomtracks * * Problem posted to comp.lang.prolog by Joel Nothman * Joel Nothman (jnothman@hotmail.com) wrote: * This problem was recently in a Mathematics competition. Although I * completed it through logic and mathematics, without the aid of a computer, * I'm wondering if and how it could be answered using prolog. * * Problem Statement * * The problem is as follows: * World theme park has seven attractions which are so far apart that there * needs to be a network of monorails, called zoomtracks, to transport the * patrons between attractions. There is exactly one zoomtrack between * each pair of attractions. Each zoomtrack can only transport patrons * in one direction.The network is constructed so that two friends can * always meet at a third attraction after exactly one trip each from any * two attractions. * Hint: Each attraction leads to and is led to by 3 other attractions. There * are 21 zoomtracks altogether.What is the entire configuaration of the * theme park if the following details exist: * (The first letter of each line is the attraction from which the zoomtrack * comes and the one beside it is where the zoomtrack leads to). * SU SO ST UO UN UP OT ON NP TU * * Solution Overview * * An interesting aspect of this puzzle is the "partial solution" given. What * is its purpose? is it supposed to help or hinder? * In fact, the partial solution allows relatively naive methods to find the * right answer in reasonable time. * However, I've chosen to implement a method that is not dependent on the * partial solution. The key to this approach is the generation of the * 'stations' data-structures, which may be partially instantiated with the * given solution, before the search for a complete solution begins. * * The requirements of the problem are that each Attraction will have three * destinations which can be reached by a single "zoom-station" and that * every pair of Attractions must have a destination in common. * This solution uses the insight that every pair of Attractions must have * exactly one destination in common. * * Program * * zoom/0 finds a solution and then prints it. */ zoom :- zoom_tracks( ZoomTracks ), print_zoom_tracks( ZoomTracks ). /* zoom_tracks( ?ZoomTracks ) holds when ZoomTracks is a set of * Attraction x Links x Destinations tuples, describing a valid configuration * of zoomtracks, such that each pair of attractions has exactly one * destination in common. * The predicate network/2 always generates viable solutions, but a * simple assertion is used to demonstrate that the solution is valid * directly. */ zoom_tracks( ZoomTracks ) :- station_origin( Station, Attraction ), station_destinations( Station, Destinations ), length( Destinations, 3 ), findall( Station, attraction( Attraction ), ZoomTracks ), findall( [Dest,Dest,Dest], attraction( Dest ), PossibleDestinations ), unified_zoomtracks( ZoomTracks ), connections( ZoomTracks ), network( ZoomTracks, PossibleDestinations ), forall( pair_of_stations( ZoomTracks, Station1, Station2 ), friends_can_meet( Station1, Station2 ) ). /* unified_zoomtracks( +ZoomTracks ) holds when ZoomTracks is a set of * Attraction x Links x Destinations tuples such that each link between to * Attractions is represented by a variable shared between the two attractions. * In each tuple, the Link variable denoting the Attraction is bound to 'self'. */ unified_zoomtracks( ZoomTracks ) :- station_origin( First, Attraction1 ), station_origin( Second, Attraction2 ), findall( Attraction1-Attraction2, pair_of_stations(ZoomTracks, First, Second), Linkage ), unified_links( Linkage, ZoomTracks ). /* unified_links( +Linkage, +ZoomTracks ) holds when Linkage is a list of * Attraction1-Attraction2 pairs such that, in ZoomTracks: * . The link variables denoting Attraction1 for Attraction2 and vice versa * are unified * . The link variables denoting Attraction1 for Attraction1 and Attraction2 * for Attraction2 are bound to 'self'. */ unified_links( [], _ZoomTracks ). unified_links( [First-Second|Linkage], ZoomTracks ) :- station_origin( Station1, First ), station_links( Station1, Links1 ), station_origin( Station2, Second ), station_links( Station2, Links2 ), memberchk( Station1, ZoomTracks ), memberchk( Station2, ZoomTracks ), link_receiver( First, Links2, Receiver ), link_receiver( Second, Links1, Receiver ), link_receiver( First, Links1, self ), link_receiver( Second, Links2, self ), unified_links( Linkage, ZoomTracks ). /* connections( +ZoomTracks ) holds when the given connections have been * applied to ZoomTracks . * Note that this can be made vacuous without any significant effect on * performance. */ connections( ZoomTracks ) :- connection( s, u, ZoomTracks ), connection( s, o, ZoomTracks ), connection( s, t, ZoomTracks ), connection( u, o, ZoomTracks ), connection( u, n, ZoomTracks ), connection( u, p, ZoomTracks ), connection( o, t, ZoomTracks ), connection( o, n, ZoomTracks ), connection( n, p, ZoomTracks ), connection( t, u, ZoomTracks ). /* connection( +Source, +Destination, +ZoomTracks ) holds when ZoomTracks * contains a connection from Source to Destination. */ connection( From, To, ZoomTracks ) :- station_origin( Station, From ), station_links( Station, Links ), station_destinations( Station, Destinations ), memberchk( Station, ZoomTracks ), memberchk( To, Destinations ), link_receiver( To, Links, To ). /* pair_of_stations( +ZoomTracks, ?Station1, ?Station2 ) holds when Station1 * and Station2 are distinct elements of ZoomTracks, avoiding redundant * solutions. */ pair_of_stations( [Station1|ZoomTracks], Station1, Station2 ) :- member( Station2, ZoomTracks ). pair_of_stations( [_Station0|ZoomTracks], Station1, Station2 ) :- pair_of_stations( ZoomTracks, Station1, Station2 ). /* friends_can_meet( +Station1, +Station2 ) holds when Station1 and Station2 * have a common destination. */ friends_can_meet( Station1, Station2 ) :- station_destinations( Station1, Destinations1 ), station_destinations( Station2, Destinations2 ), member( MeetingPoint, Destinations1 ), member( MeetingPoint, Destinations2 ). /* network( +ZoomTracks, +Destinations ) holds when ZoomTracks is a set * of attraction -> destinations pairs describing a valid configuration of * zoomtracks, such that each pair of attractions has exactly one destination * in common. Destinations defines the range of ZoomTracks . */ network( ZoomTracks, Destinations ) :- network1( ZoomTracks, Destinations, [] ). network1( [], Destinations, _Stations ) :- forall( member( Empty, Destinations ), Empty == [] ). network1( [Station|Stations], Destinations, Assigned ) :- destination_assignment( Station, Destinations, Destinations1 ), properly_connected( Station, Assigned ), network1( Stations, Destinations1, [Station|Assigned] ). /* destination_assignment( +Station, +Destinations, ?Destinations1 ) holds * when Destinations1 is the difference of Destinations and the destinations * of Station , which must not contain the origin of Station . */ destination_assignment( Station, Destinations0, Destinations1 ) :- station_destinations( Station, Destinations ), station_links( Station, Links ), matching( Destinations, Links, Destinations0, Destinations1 ). /* matching( +Destinations0, +Links, +Destinations1, ?Destinations2 ) holds * when Destinations2 is the difference of Destinations0 and Destinations1, * and the Links variables corresponding to Destinations0 are instantiated. */ matching( [], _Links, Destinations, Destinations ). matching( [Destination|Destinations], Links, Destinations0, [Rest|Destinations1] ) :- select( [Destination|Rest], Destinations0, Destinations2 ), link_receiver( Destination, Links, Destination ), matching( Destinations, Links, Destinations2, Destinations1 ). /* properly_connected( +Station, +Stations ) holds when Station and each * member of Stations have exactly one destination in common. */ properly_connected( Station, Stations ) :- station_destinations( Station, Destinations ), station_destinations( Station1, Destinations1 ), forall( member( Station1, Stations ), one_common_member( Destinations, Destinations1 ) ). /* one_common_member( ?Set0, ?Set1 ) holds when Set0 and Set1 have exactly * one common member. */ one_common_member( Set0, Set1 ) :- select( Member, Set0, Residue0 ), select( Member, Set1, Residue1 ), \+ common_member( Residue0, Residue1 ). /* common_member( ?Set0, ?Set1 ) holds when Set0 and Set1 have a common * member. */ common_member( Set0, Set1 ) :- member( Member, Set0 ), member( Member, Set1 ). % Data Abstraction attraction( Name ) :- link_receiver( Name, _Links, _Value ). link_receiver( s, links( S,_U,_O,_N,_T,_P,_Q), S ). link_receiver( u, links(_S, U,_O,_N,_T,_P,_Q), U ). link_receiver( o, links(_S,_U, O,_N,_T,_P,_Q), O ). link_receiver( n, links(_S,_U,_O, N,_T,_P,_Q), N ). link_receiver( t, links(_S,_U,_O,_N, T,_P,_Q), T ). link_receiver( p, links(_S,_U,_O,_N,_T ,P,_Q), P ). link_receiver( q, links(_S,_U,_O,_N,_T,_P, Q), Q ). station_destinations( zoom(_Name, _Links, Destinations), Destinations ). station_links( zoom(_Name, Links, _Destinations), Links ). station_origin( zoom(Name, _Links, _Destinations), Name ). % Utility Predicates :- ensure_loaded( misc ). % Load a small library of puzzle utilities. /* print_zoom_tracks( +ZoomTracks ) prints all the links in ZoomTracks as * origin - destination pairs of stations. */ print_zoom_tracks( [] ). print_zoom_tracks( [ZoomTrack|ZoomTracks] ) :- station_origin( ZoomTrack, Origin ), station_destinations( ZoomTrack, Destinations ), print_zoom_track_links( Destinations, Origin ), print_zoom_tracks( ZoomTracks ). print_zoom_track_links( [], _Origin ). print_zoom_track_links( [Destination|Destinations], Origin ) :- format( '~w~w~n', [Origin,Destination] ), print_zoom_track_links( Destinations, Origin ).