Inspired by discussion on this forum. For background, the game 504 is named as such because there are 504 possible "variations" formed by picking 3 modules from a possible 9 (where order is important). So, for example, the game formed by modules 4, 1 and 5 (aka "world 415") has victory conditions based on warfare (Module 4: Military) with income from a pick-up and deliver mechanic (Module 1) and bonus points based on exploring new territory (Module 5: Exploration). To help keep track of what rules you're playing by, a flipbook is provided (a bit like the books where you flip through a series of pictures to choose a hairstyle, eyes, nose, etc to make a face).
So the pertinent bits are:
- Each "world" is defined by a permutation of 3 digits chosen from (1, ..., 9).
- If two worlds differ only through one of the 3 digits differing by 1, you can consider them adjacent since you just have to turn one page of the flipbook to get from one to the next (so for example, world 456 is adjacent to world 356).
- Hence, you can represent the flipbook as a graph where the vertices are possible worlds and the edges represent flipping pages.
It's fairly easy to prove that as it stands, there is no Hamiltonian path through the flipbook - each of the worlds using modules 1, 2 and 3 in some order (and similarly 7, 8 and 9) has only one adjacent world, formed by flipping the 3 to the 4. Flipping either of the other pages would cause a repeated value (e.g. 223 or 113) which is not allowed in the game's construction. But having 12 worlds each with only one adjacent world means that you can't draw a nice path between them.
However, what if we assumed that modules 1 and 9 were also adjacent, so that we could flip between them? Then world 123 is adjacent to both 923 and 124, and likewise for the other problem worlds.
As far as I can tell, this graph doesn't belong to any of the nice families of groups that are guaranteed to have a Hamiltonian path. But is there one? And if so, is there a neat algorithm to follow it?
In fact this altered flipbook graph is not connected! Imagine arranging the numbers 1,..., 9 like the face of a clock, so 1 is adjacent to 2 and to 9, and that reading in clockwise order gives $1,2,\dots, 9, 1, 2$. Then call a vertex 'clockwise' if the three digits in the permutation it gives are in clockwise order, and 'anticlockwise' otherwise. So 123 is clockwise but 132 is anticlockwise.
Now no clockwise vertex can be adjacent to an anticlockwise vertex. To see this note that a vertex can be represented by three dots on the clock. Vertices are adjacent if they have two dots in common and the third dot of one vertex can be slid to the third dot of the other vertex. But sliding clearly can't change a clockwise vertex into an anticlockwise vertex.
Of course this leaves open the question of whether the clockwise vertices form a graph with a Hamiltonian path, but I have no idea where to begin with that!