Chromatic Polynomials 07 – The Catan Dice Game

The dice game version of Settlers of Catan presents a small map:

The player starts at the arrow toward the top left and fills in roads to access different settlements and cities. For example, the player must fill in two roads to access the city labeled ‘7’. Once the player has filled in the road to that city, they can fill in that city to get 7 points. (I’m glossing over the dice mechanics here to get to the CPs). The player can also fill in the knights (the “person” shapes) at the center of each hexagon, then choose to use the knight once after it is filled in.

We can use CPs to calculate the number of different states that a player’s card can be in.

Roads

First, we will define two states for each item on the card: Empty (E) or Filled (F). Then we number the roads:

The rules of the game state that roads must be built contiguously. To build a road, we must have already built all the roads leading up to it. We must build road 1 before building road 2 or 3. We must build road 3 before building road 4, and so on. Each road after road 1 needs a term to express its requirements. To require that road 1 is built before road 2, we specify a term that excludes the case where road 1 is empty and road 2 is filled:

Extending this to the other roads gives us this expression:

Evaluating this expression tells us that there are 117 ways to build roads in this game.

Settlements and Cities

Next, we assign numbers to the settlements and cities, and add terms for their road requirements.

To build a settlement or city, we must first build the roads leading to it. This gives us terms very similar to the roads. For example, building city 18 requires road 2:

Writing terms for all the settlements and cities gives us this:

Adding these terms to the expression and evaluating it yields 14,600 states:

Knights

Finally, the knights must be filled in order, e.g. knight 1 must be filled before knight 2. In the game, buying a knight gives us the opportunity to use the knight for a benefit once later in the game. Thus, Knights can have 3 states instead of 2: Empty (E), Filled (F), and Used (U). We must write an expression to specify that if Knight 1 is Empty, Knight 2 cannot be Filled or Used:

This gives us an expression for all possible game states:

Evaluating Complexity

The CountTerms function of my CP engine enables me to see how much work is involved in counting those 1.8 million possibilities. Counting each number as a term, and each extended Kronecker delta as a term, the full expression contains 87 terms:

When summing over σ₁, we need to consider all 87 terms, to see which ones needs to be expanded and summed. The result of the summation yields 85 terms for the second step to evaluate. At the third step there are 83 terms. The number of terms sometimes decreases and sometimes increases, depending on how much expansion is required at each step. The highest term count is 1,117 terms at step 16. Adding the number of terms at each step produces a total of 8,514 terms to completely evaluate the expression. That is 8,514 operations to count 1,854,200 solutions.

This shows that evaluating a Chromatic Polynomial is much more efficient than a brute force evaluation of all the possibilites.

Previous Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 06 – Sudoku

The news article that I read on Chromatic Polynomials touted Timme et al.’s work as applicable to Sudoku. The article didn’t explain how CPs could be applied to Sudoku, and Timme et al.’s paper didn’t mention it at all. I guess some journalist decided that Sudoku made for a flashier headline than “Counting complex disordered states”.But the seed was planted, and I wanted to work out how it could be done. The CP expression for Sudoku is straightforward, but very, very cumbersome:Sudoku Approach 1

Next Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 08 – Counting, Completing, Checking, Solving, and Iterating

Up to this point we have primary talked about defining a CP and then performing a summation over the vertices to produce a polynomial that tells us the number of solutions the CP has. We can use that single feature to perform a variety of functions - Counting, Completing, Checking, Solving, and Iterating.CountingThe basic function of a CP is to count the number of ways that logical conditions can be met. Let’s look at this simple CP:The logical conditions translate to: σ2 must be equal to 1 or 2