Quoridor Questions – Wall Counting Continues

I posted my original question about possible wall positions on MathSE and someone answered right away. I’m going to try and explain the method used to answer my question with a few pictures.

First, to restate the original question. I asked how many possible ways there are to put the 20 walls on the Quoridor board. For this question I’m ignoring illegal boards that block pawns or block paths to the goal. My motivation for asking the question was to whittle down Merten’s original estimate of how many total board positions there are in Quoridor.

Our answer starts by looking at the board and focusing on the vertices where walls are placed. If we narrow our view to one single row of the board, we can see one row contains 8 vertices.

What’s more is that each single vertex can take one of three values. It can be empty (no walls), it can have a horizontal wall, or it can have a vertical wall.

H: horizontal wall occupies the vertex V: vertical wall occupies the vertex X: the vertex is unoccupied

Along with this are some simple rules we have to follow. First, in one horizontal row there can’t be two “H vertices” next to each other. This would mean we have overlapping walls.

We can’t have two horizontal vertices next to each other.

The same rule will apply for vertical walls, but for now we are dealing with one row so we can stick with just our horizontal wall rule.

From here calculate the total number of ways we can arrange the 8 vertices in one row. For example we could have a row that is completely blank, a row with a few horizontal walls, or a row with 8 vertical walls.

Because there are 3 possibilities for every vertex (X, V, H), we raise 3^8 to estimate the total number of rows. This gives us 6561, but we have to subtract from this number any rows that include two Hs next to each other. I’m not sure how to do this mathematically, but you can imagine a computer program that can check all 6561 rows quickly and eliminate any that violate our rule. This leaves us with 3344 ways to build one row without placing 2 Hs next to each other.

Next we stack. With our 3344 possible horizontal rows, we can simply stack them on top of each other. This time we have to add our rule for vertical walls. If a given row includes a V vertex, then the row above it or below it may not have a V in the same column.

8 rows stacked makes one board. Again, I’m not sure about the math here, but I can imagine a computer program doing two things. First it can find all of the permutations of our various rows stacked on top of each other in sets of 8, or, in other words, all possible boards. Then it can go through this list of boards and eliminate any that violate our rules about two V vertices in the same column.

This leaves us with one final check. Following our logic so far we could have a board of entirely vertical walls. This wouldn’t violate any of our previous rules, but it would violate the limit of 20 walls in a game of Quoridor. To solve this again we have to imagine a computer program checking each board.

Starting with the top row of a given board the computer would count the walls in that row. Moving on to the next row the computer would count the walls in that row and keep a running total. If we get over 20 then we know it is an illegal board and we can eliminate from our final set.

So the answer???

 

If you haven’t checked out the answer posted on MathSE I strongly recommend it. I think the author does a great job of explaining it, and he even took the time to answer my follow up questions. Thanks!