I learned about the game of Quoridor when my sister begged me to play the game with her husband. “Somebody’s got to beat him at it!” she said. I beat him once, and then he upped his game and I haven’t beat him since. But the game gave me something to think about:
How many ways can you place fences on the board?
Fence Placement Rules
Here’s what the Quoridor board looks like:
You can find the rules for Quoridor here: https://en.wikipedia.org/wiki/Quoridor. For now, we only need to know the following:
• The board is 9x9 grid of squares on which pawns can be placed.
• Between the squares, you can place “fences”. A fence can be placed horizontally or vertically. The fence must be centered at the intersection of four squares.
• There are 20 fences and when those run out, no more fences can be added.
To consider how to place fences, we only need to consider the 8x8 grid of intersections between the 9x9 grid of squares. Each intersection can have no fence, a horizontal fence, or a vertical fence. The only limitations are:
• Players cannot place two horizontal fences at two horizontally adjacent intersections. It’s not physically possible, since they would overlap in the area between the intersections.
• For the same reason, players cannot place two vertical fences at two vertically adjacent intersections.
• Players can place anywhere from 0 to 20 fences.
A First (Impractical) Approach
I first tried to calculate the ways to place each number fences:
• 0 fences – There is 1 way to place 0 fences on the board.
• 1 fence – There are 64 intersections and the fence can be either horizontal or vertical, so there are 64 * 2 = 128 ways to place one fence.
• 2 fences – There are 64C2 = 64 63 / 2 = 2,016 ways to select two intersections. Multiply that by 2 ways to orient each fence and we get 2,016 2 2 = 8,064 ways. However, some of these include two horizontally adjacent horizontal fences or two vertically adjacent vertical fences, which we must subtract. There are 7 positions for two horizontally adjacent intersections in a single row. 7 8 rows = 56 placements of two horizontal fences to exclude. There are also 56 placements of two vertical fences to exclude, so the final number is 8,064 - 2 * 56 = 7,952.
I got as far as calculating the number of ways to place 3 fences. It got very complex, very fast and I quickly realized that I was not going to get much further this way.
Prior Art
I found a paper published on June 21, 2006 by P.J.C. Mertens (available here), in which the number of ways to place fences is estimated as:
It’s an impressive approach. But I realized that it was possible to do much better than this estimate – in fact, it’s possible to calculate the exact number!
Handling a Single Row
I will first calculate the number of ways to place fences in a single row of 8 intersections, filling one intersection at a time.
For the first intersection, the count is easy:u
Fence | Ways |
|---|---|
No Fence | 1 |
Vertical Fence | 1 |
Horizontal Fence | 1 |
The number of ways to fill the 2nd intersection depends on what is in the first intersection:
• If the first intersection has either no fence or a vertical fence, the second intersection can have anything - no fence, a horizontal fence, or a vertical fence.
• If the first intersection has a horizontal fence, the second intersection cannot have a horizontal fence. It must have either no fence or a vertical fence.
We can reduce this to:
F(n, p) = The number of ways to fill n intersections where fence p is placed in the last intersection. P can be E for Empty, V for Vertical, or H for Horizontal.
F(n, E) = F(n - 1, E) + F(n - 1, V) + F(n - 1, H)
F(n, V) = F(n - 1, E) + F(n - 1, V) + F(n - 1, H)
F(n, H) = F(n - 1, E) + F(n - 1, V)
Since the formulas for F(n, E) and F(n, V) are the same, we can reduce this to:
F(n, E or V) = 2 * (F(n - 1, E or V) + F(n - 1, H))
F(n, H) = F(n - 1, E or V)
This quickly gets us this table:
Intersection | ||||||||
|---|---|---|---|---|---|---|---|---|
Last Fence | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
E or V | 2 | 6 | 16 | 44 | 120 | 328 | 896 | 2,448 |
H | 1 | 2 | 6 | 16 | 44 | 120 | 328 | 896 |
Total | 3 | 8 | 22 | 60 | 164 | 448 | 1,224 | 3,344 |
The only insight here is that you don’t need to know the placement of all intersections - you only need to know the fence placement at the last intersection and the number of ways to reach that last placement.
Two Dimensional Calculations
To expand this to two dimensions, I don’t need to know how all the previous rows were filled – I only need to know the last row.
I first reduced each of the 3,344 row arrangements to an 8-bit “signature”, with one bit for each intersection. The signature has a 1-bit if there is a vertical wall in that intersection and a 0-bit if the intersection is empty or has a horizontal wall. The signature structure also contains a fence count and a ways count. Some sample entries are shown in the table below. In the Ways column, the explicit fence placements are shown using 0 for no fence, 1 for a vertical fence, and – for a horizontal fence:
Signature | Fences | Ways | Data Structure |
|---|---|---|---|
10010100 | 3 | 1: 10010100 | Sig.Signature = 10010100 Sig.Fences = 3 Sig.Ways = 1 |
10010100 | 4 | 5: 1–010100 10–10100 1001–100 100101–0 1001010– | Sig.Signature = 10010100 Sig.Fences = 4 Sig.Ways = 5 |
10010100 | 5 | 8: 1–01–100 1–0101–0 1–01010– 10–1–100 10–101–0 10–1010– 1001–1–0 1001–10– | Sig.Signature = 10010100 Sig.Fences = 5 Sig.Ways = 8 |
10010100 | 6 | 4 1–01–1–0 1–01–10– 10–1–1–0 10–1–10– | Sig.Signature = 10010100 Sig.Fences = 6 Sig.Ways = 4 |
At N rows, I have a two-dimensional array of ways to the intersections with fences:
Ways_At_Row_N [signature] [fences_used]These are initialized to zero. To fill the next row two signatures, SigA and SigB, are compatible if the binary AND operator produces zero: SigA.Signature & SigB.Signature == 0. This check ensures that there won’t be two vertically-adjacent vertical walls.
If they are compatible, then I add the ways to the next row:
For each possible value of Curr_Fences (0 to 20):
Curr_Ways = Ways_At_Row_N [SigA.Signature] [Curr_Fences]Ways_At_Row_N+1 [SigB.Signature[ [Curr_Fences + SigB.Fences] += Curr_Ways * SigB.WaysThe code for this is in https://github.com/telemath/Quoridor1. It takes approximately 3 seconds to run.
Here are the resulting counts:
Fences | Ways` |
|---|---|
0 | 1 |
1 | 128 |
2 | 7,952 |
3 | 319,520 |
4 | 9,336,404 |
5 | 211,491,832 |
6 | 3,866,372,136 |
7 | 58,636,760,064 |
8 | 752,598,563,471 |
9 | 8,299,064,015,840 |
10 | 79,553,115,046,808 |
11 | 669,107,731,222,152 |
12 | 4,975,324,689,992,572 |
13 | 32,909,303,106,095,952 |
14 | 194,630,399,392,814,948 |
15 | 1,033,594,027,192,431,392 |
16 | 4,946,375,599,891,710,379 |
17 | 21,395,456,537,906,592,712 |
18 | 83,857,388,242,244,068,776 |
19 | 298,437,313,361,130,100,776 |
20 | 966,064,728,491,347,230,956 |
Total | 1,375,968,129,062,134,174,771 |
There we have it. There are exactly 1,375,968,129,062,134,174,771 or 1.376x10^21 ways to place 0 to 20 walls on a Quoridor board!
Yes, But: This doesn’t consider pawn placements or the rule that the walls cannot completely block a pawn from reaching its goal. There are 81 ways to position the first pawn and 80 ways to position the second. This includes 81 ways in which both pawns have reached their goal, which is impossible. So there are 81 80 - 81 = 6,399 ways to position the pawns. So there will be fewer than 6,399 1.376 x 10^21 = 8.805 x 10^24 states in the entire game. I have plans for incorporating pawns and calculating the exact number of game states, but I haven’t written that program yet.
Another Approach
Some time after creating the first Quoridor calculation program, I realized that I could simplify the use of signatures by filling one intersection at a time and tracking only the last 8 intersections filled using this logic:
• The intersection may always be empty.
• The intersection may contain a vertical wall only if the intersection is in the first row or the intersection directly above it does not contain a vertical wall.
• The intersection may contain a horizontal wall only if the intersection is in the first column or the intersection to the left does not contain a horizontal wall.
With this approach, I don’t have to track row arrangements and their signatures – I can go directly from all the ways to fill N intersections to all the ways to fill N + 1 intersections. For example, from this state:
... | ... | ... | ... | ... | ... | ... | |
... | 0 | | | – | | | 0 | 0 | | |
– |
The next possible states are:
... | ... | ... | ... | ... | ... | ... | ... |
... | 0 | | | – | | | 0 | 0 | | |
– | 0 |
or
... | ... | ... | ... | ... | ... | ... | ... |
... | 0 | | | – | | | 0 | 0 | | |
– | | |
The base operation for this is:
If (some fence option is allowed in this state) NextState.ways += ThisState.ways;Since the base operation for this approach is addition, I was curious about how many additions were involved in running the program from start to finish, so I had the program count those. It performed 17,576,673 additions – that’s all it takes to do all its work!
The code for this is in https://github.com/telemath/Quoridor2. I wrote this version in C#, so it’s slower than the C++ version. It takes approximately 10 seconds to run. Of course, it produces the same results as Quoridor1.
The Moral of the Story
It would be pretty much impossible to count the number of ways to fill a Quoridor board by checking all the possibilities. It’s also extremely complicated to try to write a formula for each number of walls placed.
But if all you want is the number, then you don’t need to know the actual arrangements – and it’s quite simple to calculate that number.
This highlights an important rule for efficient calculation. If your computations are running slow, one way to speed it up is to look at all the interim data that is produced on the way to the final answer. Then, look for a way to find the same answer without producing that interim data. I use this rule when I’m looking for ways to speed things up:
If you are producing more information than you want, then you are doing more work than you need to.
Comments