1
$\begingroup$

In the picture below, each node represents a train station. On each node there is a train. Two trains can change the location / node they are in, if they are connected by an arrow. The puzzle is this:

[[1, 2], [7, 4], [3, 5]]

  • 1 wants to change place with 2
  • 7 wants to change place with 4
  • 3 wants to change place with 5
  • 6 should remain in the same position after all moves, but it can change its position in between

Is there a way to move the trains so that no two trains are at the same location and the puzzle above is solved?

coorinating_trains_puzzle

I have a solution, but I want to hear your opinion for other ways to solve it. (I made this puzzle.)

I should add that it is possible for a train to wait at a station in a timestep.

Edit: The trains should move simultaneously and have finished swapping after the same number of time steps.

Here is one possible solution with $12$ time steps starting at $t=1$ and ending at $t=12$.

Here are the three rules clarified:

  1. There are no two trains at the same station at each time step.

  2. One move consists of: One train can stay on the same station at one time step, or be swapped by one of its neighbors.

  3. All trains "move" simultaneously (where move is defined in the sentence above).

I hope it is clearer now.

[1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 2]
[2, 1, 3, 6, 6, 6, 3, 1, 2, 2, 1, 1]
[3, 3, 1, 1, 1, 5, 5, 5, 5, 5, 5, 5]
[4, 4, 4, 4, 2, 2, 6, 3, 1, 7, 7, 7]
[5, 5, 5, 5, 5, 1, 2, 6, 3, 3, 3, 3]
[6, 6, 6, 3, 3, 3, 1, 2, 6, 6, 6, 6]
[7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 2, 4]

Second Edit: What is the least number of moves to solve this puzzle?

$\endgroup$
7
  • 6
    $\begingroup$ Did you maybe forget a rule? It looks as though a simple set of swaps should be sufficient as a solution to the puzzle as stated. In particular, there's no need to ever move train 6 $\endgroup$ Feb 26, 2023 at 22:12
  • $\begingroup$ Reading the solutions provided so far, it looks like everyone is just swapping pairs of trains individually. I read this as allowing any movements of trains along edges of the graph as long as you don't end up with two at one location, so for example, 2,1,3,6 could all rotate positions in one move. $\endgroup$
    – fljx
    Feb 28, 2023 at 9:08
  • $\begingroup$ Maybe the OP could edit the question to clarify. $\endgroup$
    – fljx
    Feb 28, 2023 at 9:09
  • 1
    $\begingroup$ This needs more info. Is this single track (i.e. can 1 and 2 simply swap in one move)? Can a train park on the track? (Normally in graph theory, edges can't hold anything) Can more than one train park on the same track? VTC: Details or Clarity $\endgroup$ Feb 28, 2023 at 13:58
  • $\begingroup$ @ChrisCudmore: I updated the question. $\endgroup$ Feb 28, 2023 at 16:05

4 Answers 4

4
$\begingroup$

If only swaps are used, then the minimum number of swaps is

9

and there are many such solutions, some of which are given in the other answers. All of these keep 6 stationary. Here is one:

1234567 swap 1,5
5234167 swap 5,7
7234165 swap 2,7
2734165 swap 1,2
1734265 swap 4,7
1437265 swap 4,1
4137265 swap 4,5
5137264 swap 3,5
3157264 swap 2,3
2157364

   5     1     1     1     2     2     2     2     2     3
 4217  4257  4275  4725  4715  7415  7145  7154  7134  7124
  63    63    63    63    63    63    63    63    65    65

There is another kind of move available, namely

a 4-cycle of the trains around the main loop in the network.

If this counts as a single move then there are shorter solutions, with the minimum of

7 moves.

1234567 swap 1,7
7234561 cycle 7,3,6,2
3764521 swap 3,5
5764321 swap 4,7
5467321 cycle 5,4,2,6
4257361 swap 1,4
1257364 swap 1,2
2157364

   5     5     5     3     3     3     3     3
 4217  4271  4731  4751  7451  7241  7214  7124
  63    63    26    26    26    65    65    65

Suppose however that simultaneous disjoint swaps count as a single move. Then the optimal solutions have

6 moves:

1234567 swap 1,3
3214567 swap 3,5;2,6
5614327 swap 5,7;4,6
7416325 swap 4,7;1,2
4726315 swap 4,5;6,7
5627314 swap 2,5;1,6
2157364

   5     5     3     3     3     3     3
 4217  4237  4657  6475  6745  7654  7124
  63    61    21    21    12    12    65

$\endgroup$
3
  • 1
    $\begingroup$ This is the best answer. $\endgroup$ Mar 1, 2023 at 13:23
  • $\begingroup$ Best answer so far indeed. Jaap, do you also claim minimality for the cycle and simultaneous swap? $\endgroup$
    – justhalf
    Mar 2, 2023 at 9:07
  • 1
    $\begingroup$ @justhalf Yes, these should all be optimal as I used a breadth-first-search by computer. $\endgroup$ Mar 2, 2023 at 9:14
1
$\begingroup$

I think this covers all optimal solutions:

Move 4 toward 7's starting position, three times. Move 7 toward 4's starting position, twice.

Move 3 toward 5's starting position, twice. Swap 5 into 3's starting position.

Swap 1 and 2.

These sets of moves can be rearranged, and the first two can have their individual steps inverted. So that's 24 ways to do it in 9 swaps.

$\endgroup$
2
  • 1
    $\begingroup$ The OP states "no two trains are at the same location" so all moves must be swaps. I don't follow your moves at all. $\endgroup$ Feb 26, 2023 at 21:37
  • $\begingroup$ @WeatherVane Read each instance of "move" as "swap with the train that is in the spot it is moving to". $\endgroup$ Feb 28, 2023 at 8:22
1
$\begingroup$

IIUC:

Swap 7,1 7,2 7,4 4,2 4,1 3,1 3,5 1,5 1,2

$\endgroup$
1
$\begingroup$

This puzzle seems rather trivial to me, especially if we're simply looking for a solution, rather than trying to find a solution that optimizers for some constraint.

We can swap a "spur" train with a "central" one. For instance, to swap Train2 and Train6:

Train2 goes towards Train6. Train6 goes to where Train2 was, then travels past towards Train1. Train2 goes to where Train6 was. Train6 goes to where Train2 was.

We can swap two "central" trains:

If we want to swap $T_a$ and $T_b$, we rotate the "central" trains until $T_a$ is in Node2, then swap it with Node4, then we rotate until $T_b$ is in Node2 and swap Node2 and Node4. Then rotate until the other two trains are in their original locations.

Since the set of permutations is generated be swaps, this proves a solution exists (and it's a constructive proof).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.