Consider the following Hexagon, composed of 19 smaller hexagons. The smaller Hexagons are each either Purple, Yellow, or Green, based on how many other hexagons border them:
*A hexagon that only touches 3 others is Green
*A hexagon that only touches 4 others is Yellow
*A hexagon that touches 6 others is Purple, except for the one at the very center which is Green
So the Hexagons are arranged like so:
Hex Hex Hex
Hex Hex Hex Hex
Hex Hex Hex Hex Hex
Hex Hex Hex Hex
Hex Hex Hex
We're going to assign each hexagon a number, from 1 to 19, so that each number appears in one and only one hexagon. When placing the numbers, two rules must be followed:
1) Each number is assigned a color; just like the hexagons, they can be Green, Yellow, or Purple. Each number must be placed on a hexagon of the same color.
*Green Numbers: 2, 3, 6, 10, 14, 17, 18
*Yellow Numbers: 4, 7, 9, 11, 13, 16
*Purple Numbers: 1, 5, 8, 12, 15, 19
2) Two hexagons that share a border can't have numbers with a difference of 1 (for example, the hexagon with a 6 on it can't be touching one with a 5 or 7 on it).
(Right off the bat we can tell that the center hexagon, being a green hex that borders all 6 purple hexes, must have either a 3, 10, or 17 on it, as the other green numbers are all one away from one of the purple numbers.)
Arranging the numbers in a way that follows all the rules is easy. What I'm trying to figure out is how many legal arrangements exist (and from there how to write an algorithm that would randomly generate a legal arrangement, but I suspect that any proof for the answer to the former will give me all the info I need for the latter). Position of the numbers is relevant, so any rotations or reflections of a given arrangement count as separate arrangements provided they don't end with all the numbers in the exact same place.
(For the curious, this is intended to be part of a larger algorithm I'm devising that generates maps for Settlers of Catan)
Catanese Starburst
Moderators: gmalivuk, Moderators General, Prelates
 Lopsidation
 Posts: 183
 Joined: Tue Oct 27, 2009 11:29 pm UTC
Re: Catanese Starburst
Brute force. Speed it up with backtracking or "WLOG this hex is 19". There won't be a nice mathematical argument.
EDIT: Are there even any solutions at all?
EDIT: Are there even any solutions at all?
Re: Catanese Starburst
Lopsidation wrote:Brute force. Speed it up with backtracking or "WLOG this hex is 19". There won't be a nice mathematical argument.
EDIT: Are there even any solutions at all?
There are solutions (2, 4, 6 // 7, 8, 1, 9 // 10, 5, 17, 12, 14 // 13, 15, 19, 16 // 18, 11, 3)
(Purple, yellow, green )
1, 5, 8, 12, 15, 19
4, 7, 9, 11, 13, 16
2, 3, 6, 10, 14, 17, 18
Ignoring the green tiles, it comes down to counting the number of ways you can arrange purple yellow purple yellow without connection issues (purple has no connections with itself)
Let's start with purple
1 can connect to all six: six possible neighbors
5 cannot for 4 only : five possible neighbors
8 not for 7 and 9 : four possible neighbors
12 not for 11 and 13: four possible neighbors
16 not for 17: five possible neighbors
19 not for 18: five possible neighbors
Probably drawing the graph would make it easier to count the cycles in the graph.
I expect that all permutations of purples have a valid solution; thus I recommend choosing the purples randomly (6!), then the yellows, then the greens. However, if certain pur(plemutations) have less possibilities than others, then those configurations will be slightly more likely
 Lopsidation
 Posts: 183
 Joined: Tue Oct 27, 2009 11:29 pm UTC
Re: Catanese Starburst
But 7 is next to 8, breaking OP's rule 2.Elmach wrote:There are solutions (2, 4, 6 // 7, 8, 1, 9 // 10, 5, 17, 12, 14 // 13, 15, 19, 16 // 18, 11, 3)

 Posts: 2
 Joined: Thu Dec 25, 2014 4:12 am UTC
Re: Catanese Starburst
06 13 10
11 01 05 16
17 08 03 12 02
04 15 19 07
18 09 14
That one should check out.
11 01 05 16
17 08 03 12 02
04 15 19 07
18 09 14
That one should check out.
Re: Catanese Starburst
There are offtheshelf tools that will solve problems like these. Get a constraint solver and formulate this problem in terms of constraints. Generate all the solutions. To get a random sample from the distribution, randomly pick a solution with equal probability.
If you want to write the code yourself, you can write it as searching a tree, where each node of the tree represents a partial assignment of values to hexagons, and each edge represents adding an assignment of a value to a hexagon. You prune the subtrees that do not satisfy the constraints. To speed the search, select the hexagon that has the fewest remaining possible values that satisfy the constraints. I would go with a simple depthfirst search, which is easy to implement as a recursive function.
If you want to write the code yourself, you can write it as searching a tree, where each node of the tree represents a partial assignment of values to hexagons, and each edge represents adding an assignment of a value to a hexagon. You prune the subtrees that do not satisfy the constraints. To speed the search, select the hexagon that has the fewest remaining possible values that satisfy the constraints. I would go with a simple depthfirst search, which is easy to implement as a recursive function.
Who is online
Users browsing this forum: No registered users and 9 guests