Chromatic Polynomials 05 – Counting Quoridor Fence Arrangements
- Aug 23
- 3 min read
Updated: Aug 27
In this article, I showed how to calculate the number of ways that walls can be placed in the game of Quoridor (please see that article for a description of the game). Now I will show how to do it with CPs.
We will define one vertex for each intersection where a wall can be placed, σ0 through σ63. The first row contains σ0 through σ7, from left to right. The second row contains σ8 through σ15, and so on:
Named Constants
Each vertex can take one of three values – no fence (or an empty intersection), a horizontal fence, or a vertical fence. To make the CPs easier to read, we can use E (empty) =1, H (horizontal) = 2, and V (vertical) = 3. To specify that σ0 and σ1 cannot both have horizontal fences, we write:
Repeating this through the entire board will give us:
Adding the restrictions for vertical fences gives us this complete Quoridor expression, X:
This creates 112 terms. Writing X out longhand would start like this:
This can be simplified somewhat by noting that the terms with {H} and the terms with {V} will always reduce to 0:
Now the first few terms look like this:
This is one of those cases where we want to sum over a concrete range – the three possible values for each vertex – and not from 1 to Q. Summing each vertex from 1 to 3 yields this number of possible arrangements:
Of course, this is the wrong answer for the actual game. This allows for any number of fences, from 0 to 64. The Quoridor game only has 20 walls. We must find a way to exclude the ways to place 21 to 64 walls.
The CP syntax can count the number of ways that logical conditions can be met, but it’s not well suited for counting the number of occurrences of a specific value. For that, we will need a workaround.
Summing over a specific subset of values
We can accomplish our goal by limiting the range of each vertex before summing over it:
Note that both summations together include all the ways returned by:
Then, we can define a recurrence relation to count the number of ways to place each number of walls:
Processing this recurrence relation yields the following counts:
F(64,0)= | 1 |
F(64,1)= | 128 |
F(64,2)= | 7,952 |
F(64,3)= | 319,520 |
F(64,4)= | 9,336,404 |
F(64,5)= | 211,491,832 |
F(64,6)= | 3,866,372,136 |
F(64,7)= | 58,636,760,064 |
F(64,8)= | 752,598,563,471 |
F(64,9)= | 8,299,064,015,840 |
F(64,10)= | 79,553,115,046,808 |
F(64,11)= | 669,107,731,222,152 |
F(64,12)= | 4,975,324,689,992,572 |
F(64,13)= | 32,909,303,106,095,952 |
F(64,14)= | 194,630,399,392,814,948 |
F(64,15)= | 1,033,594,027,192,431,392 |
F(64,16)= | 4,946,375,599,891,710,379 |
F(64,17)= | 21,395,456,537,906,592,712 |
F(64,18)= | 83,857,388,242,244,068,776 |
F(64,19)= | 298,437,313,361,130,100,776 |
F(64,20)= | 966,064,728,491,347,230,956 |
Total | 1,375,968,129,062,134,174,771 |
|
|
This exactly matches the results calculated using a different method, in this article.
This exercise shows us that:
We can sum vertices over different ranges by multiplying an expression by an extended Kronecker delta that limits each vertex to the desired range.
We can use these ranges to count the number of vertices that match specific values.
Evaluating Complexity
I used the CountTerms function of my CP engine to count the number of terms at each step of summation, where a term is an Extended Kronecker Delta or a constant. In all, the engine processed 12,535,359 terms. These 12 million terms counted 1.3x10²¹ solutions to the problem of Quoridor wall placement, so it’s clear that evaluating a CP is not the same as a brute force approach to inspect and count each one of the 3^64 possibilities. Nor is it even comparable to a tree traversal which prunes branches when an impossibility is met, as that would still yield 1.3x10²¹ leaf nodes to visit.
Previous Article:
Next Article:
Comments