Catanese Starburst

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

XionGaTaosenai
Posts: 2
Joined: Thu Dec 25, 2014 4:12 am UTC

Catanese Starburst

Postby XionGaTaosenai » Thu Dec 25, 2014 6:02 am UTC

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)

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Catanese Starburst

Postby Lopsidation » Fri Dec 26, 2014 2:00 am UTC

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?

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

Re: Catanese Starburst

Postby Elmach » Fri Dec 26, 2014 3:20 am UTC

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(ple|mutations) have less possibilities than others, then those configurations will be slightly more likely

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Catanese Starburst

Postby Lopsidation » Fri Dec 26, 2014 2:17 pm UTC

Elmach wrote:There are solutions (2, 4, 6 // 7, 8, 1, 9 // 10, 5, 17, 12, 14 // 13, 15, 19, 16 // 18, 11, 3)
But 7 is next to 8, breaking OP's rule 2.

XionGaTaosenai
Posts: 2
Joined: Thu Dec 25, 2014 4:12 am UTC

Re: Catanese Starburst

Postby XionGaTaosenai » Mon Dec 29, 2014 6:31 am UTC

---06 13 10
--11 01 05 16
17 08 03 12 02
--04 15 19 07
---18 09 14

That one should check out.

schapel
Posts: 244
Joined: Fri Jun 13, 2014 1:33 am UTC

Re: Catanese Starburst

Postby schapel » Thu Jan 01, 2015 6:34 pm UTC

There are off-the-shelf 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 depth-first search, which is easy to implement as a recursive function.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 50 guests