### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

27 January 2017

Posted by on **From New Scientist #1530, 16th October 1986** [link]

Come with us now to those 10 Pacific islands with the quaint native names A, B, C, D, E, F, G, H, I, J. These are served by Lamour and Sarong airlines. Each morning one plane from each airline leaves each island bound for another of the islands. No two planes from the same airline are going to the same island and the two planes leaving any island go to different destinations.

The planes all carry out the return journeys overnight and everything is repeated the next day and so on.

Each island has a beautiful queen. One morning, each queen left her island on the Lamour plane, staying overnight on the island she reached, and left the next morning on the Sarong plane. At the end of their two-day journey the queens of A, B, C, D, E, F, G, H, I, J found themselves on the islands of C, F, B, H, J, D, E, I, G, A, respectively.

Some time later, the queens made similar journeys, again starting from their home islands, but this time taking the Sarong planes on the first day and the Lamour planes on the second day. This time the Queens of A, B, C, D, E, F, G, H, I, J ended up on the islands of J, A, B, I, F, H, E, C, G, D respectively.

As the sun slowly sits in the west we say a fond farewell to a £10 book token, which will be sent to the first person to tell as the details of the 10 Lamour routes.

[enigma381]

Advertisements

%d bloggers like this:

This Python program runs in 43ms.

Solution:The routes from Lamour are: A → F; B → C; C → H; D → A; E → G; F → B; G → I; H → J; I → D; J → E.The program works by choosing a destination for airline

Lflying fromA, and then infers the remaining destinations for both airlines. If it some point it finds a departure/destination pair that are the same, or a route that is duplicated between the airlines it stops looking.So, for example, if we suppose that

Lflies fromAtoB(we writeL[A] = B), then we see that the Queen ofA, flying onLand thenSarrives atC. SoS[L[A]] = C, henceS[B] = C. We now have a value forS[B], and we see that the Queen ofB, flying onSthenLarrives atA. SoL[S[B]] = A, henceL[C] = A. And we repeat the process. The Queen ofCflying onLthenSarrives atB, soS[L[C]] = B, henceS[A] = B. But we already haveL[A] = Band the airlines fly to different destinations from the same island, so this is not a valid solution.We can similarly try the other possibilities for

L[A]manually, and we find there is only one valid solution:So the solution is found when

L[A] = F.We can also express the problem as a set of constraints in MiniZinc as follows:

(This program uses my

minizinc.pywrapper library to let me do the formatting of the results in Python).This finds the solution in 162ms (using the

mzn-gecode -asolver).Here’s a slightly improved Python 3 version of the code. It doesn’t use exceptions when invalid solutions are detected, instead

assign()returns a boolean value. And the code to try the possibilities is now placed in asolve()function, which should make it work in the more general case. (Of course in this case it still only needs to consider possible values forL[A]).Not sure whether it follows automatically, but in my solution the other airline flies routes

A – H, B – D, C – F, D – G, E – A, F – C, G – J, H – B, I – E, J – I.

Yes, that’s right. These are the only solutions for

LandS.I should probably have mentioned the routes for

Sexplicitly in my comment (although there are given in my explanation of the manual solution).Lis a single cycle:(A F B C H J E G I D).Shas two cycles:(A H B D G J I E) (C F).