2
$\begingroup$

I'm trying to figure out how many possible board positions there are for the game Quoridor. I think sorting out the legal positions from the illegal positions will be difficult, so to start I'm trying to count the total number of board positions ignoring legality.

The board is 9x9. There are 81 spaces and two pawns. There are also 20 walls and 128 wall slots.

Counting pawn positions is easy (81x80 = 6480). I'm interested in counting all possible wall positions. I'm counting legal and illegal positions for now because I think it will be too hard to separate them.

To get a high estimate I followed P.J.C Mertens in his paper on the subject (check the bottom of the Quoridor Wikipedia page, I can't post more than one link yet). The synopsis is to start with a blank board, count the positions, add a wall, multiply the wall by the available positions, then decrease the available positions, add a second wall, etc.

The answer comes out to 6.1582 x 10^38. You can see a concise equation in this image.

A quote from P.J.C that shows the equation: http://i.imgur.com/8GFCmdl.png

To finish with the estimate multiply this large number by the total possible pawn positions and we get another huge number.

I'm trying to complete a more precise counting of all possible wall positions. This previous estimate ignores some important information.

For most wall slots on the board, when a wall is placed into it 4 wall slots are blocked. The slot the wall is in, the slot the wall crosses, and the two slots the wall touches. If you look at a Quoridor board (I can't post more than one link) you can see that there are 32 walls slots that touch the edge of the board. When a wall is placed in one of these 32 slots it only blocks 3 other wall slots.

So for the above example, every time you add a wall to the board it may take away 3 or 4 available slots. I'm not sure how to factor this into the equation.

Can anyone help?

$\endgroup$
  • $\begingroup$ The main problem isnt the positions of pawns or tablets, the problem is the symmetric repeated board-states. You can get the number of P.J.C and apply on them algorithms to eliminate repeated boards or impossible boards states. Symmetries are specular and rotational and maybe some other type. $\endgroup$ – Masacroso Oct 1 '14 at 8:49
1
$\begingroup$

An alternative way of looking at the wall positions would be to think in terms of intersection points instead of slots. In this model, the board has an 8x8 grid of intersection points; each intersection point can be the midpoint of a horizontal wall; the midpoint of a vertical wall; or "free". Then the non-overlap rules say that you can't have two horizontally adjacent horizontal-wall intersection points or two vertically adjacent vertical-wall intersection points.

If we look only at the rows and the horizontal walls, there are 55 possibilities. (This could be tackled as a basic problem in combinatorics on words, although I admit that I cheated and computed it). If we assume that each row is independent, each column (looking at vertical rather than horizontal walls) is independent, and there's no limit on the number of walls, we get an upper bound of $55^{16} \approx 7 \times 10^{27}$ positions, which is already a massive improvement. Restricting to 20 walls and excluding the cases which put a vertical and a horizontal wall at the same point would reduce this number considerably, but it's already much lower than Mertens' estimate.

If we instead start by focussing on the number of walls, we get an upper bound of $$\sum_{i=0}^{20} 2^i \binom{64}{i} \approx 2.6\times 10^{22}$$

To actually enumerate the possibilities I would take a programming approach. Each row has $3^8 = 6561$ possible arrangements of $V$, $H$, or $X$. Once we exclude those which have $HH$ as a substring there are $3344$ possibilities left. You can build a graph which places an edge between two of those $3344$ cases iff they don't have a $V$ at the same offset. Then the total number of wall placements (ignoring the limit of 20) is the number of paths of length 7 in the graph. (For elaboration, see the footnote). To take the limit into account you can either weight the nodes and count paths of less than a certain weight or you can construct a slightly different graph whose nodes are a pair (row arrangement, walls placed). Then the running time of a simple non-naïve count would be on the order of $3344^2 \times 20 \times 8$ times a small number of basic operations.

Assuming that I don't have any bugs in my program, I make it $$1,375,968,129,062,134,174,771$$


Elaboration on the graph:

The nodes are strings like $VHXXXXHX$ of 8 intersection points with no double-$H$. In this example, the first is the midpoint of a vertical wall, the second and seventh are midpoints of horizontal walls, and the others are not mid-points of any wall.

There are edges from $VHXXXXHX$ to every node except ones which also start with $V$, because if we put another row starting $V$ below it we'll have vertically adjacent $V$s.

So a valid board consists of 8 rows such that each pair of adjacent rows avoids vertically adjacent $V$s. E.g. the trivial board is one valid board: $$XXXXXXXX\\ XXXXXXXX\\ XXXXXXXX\\ XXXXXXXX\\ XXXXXXXX\\ XXXXXXXX\\ XXXXXXXX\\ XXXXXXXX$$ So is a board which alternates $VHXXXXHX$ and its reverse: $$VHXXXXHX\\ XHXXXXHV\\ VHXXXXHX\\ XHXXXXHV\\ VHXXXXHX\\ XHXXXXHV\\ VHXXXXHX\\ XHXXXXHV$$

Because the edges in the graph correspond to rows which can be adjacent to each other, and because there are 7 adjacent pairs in 8 rows, the valid boards correspond to the paths of length 7 in the graph.

As noted, this doesn't take into account the limit of 20 walls. The approach I've taken in the code linked above is to replace each node with 21 nodes consisting of (row, total walls). Then each board starts with (row, number of walls in the row) and the edges take into account adding the walls. E.g. the second board is now excluded, because it would be $$\begin{eqnarray*}VHXXXXHX&,&3\\ XHXXXXHV&,&6\\ VHXXXXHX&,&9\\ XHXXXXHV&,&12\\ VHXXXXHX&,&15\\ XHXXXXHV&,&18\\ VHXXXXHX&,&21\\ XHXXXXHV&,&24\end{eqnarray*}$$ and the last two aren't nodes in the graph, because the numbers exceed 20. But if we remove the walls from the last two rows we get $$\begin{eqnarray*}VHXXXXHX&,&3\\ XHXXXXHV&,&6\\ VHXXXXHX&,&9\\ XHXXXXHV&,&12\\ VHXXXXHX&,&15\\ XHXXXXHV&,&18\\ XXXXXXHX&,&18\\ XXXXXXXX&,&18\end{eqnarray*}$$ which is valid and is counted by the program.

$\endgroup$
  • $\begingroup$ Thank you so much! I want to give you a hug! I lost you in two places: I'm not sure how to get the number 55 when looking at just horizontal wall possibilities (but I'm also not sure this is important with your final calculation). In your last paragraph I don't understand the part about "paths of length 7 in the graph." Any chance you can elaborate? $\endgroup$ – lameK Oct 11 '14 at 21:52
  • $\begingroup$ @lameK, I got 55 by writing a short computer program, but as I used an obscure language to do it I didn't see any benefit to sharing it. I'll add some examples to the last paragraph. $\endgroup$ – Peter Taylor Oct 12 '14 at 7:33
  • $\begingroup$ Sorry I've looked at this a bit and thought about it but I'm still having trouble. I'm going to explain my understanding and hopefully you can point out where I go wrong. Looking at a single row of 8 intersections, we can compute all possible distributions of X, V, and H intersctions, keeping the "no two adjacent H intersections" rule. We then look at all possible "stacks" of 8 rows and eliminate any stacks that don't follow the "no two V intersections vertically adjacent" rule. This gives us the total number of possible boards. $\endgroup$ – lameK Nov 4 '14 at 14:46
  • $\begingroup$ This sounds like what you are describing in your follow up paragraphs (thank you for thoes), but I couldn't make the connection between these ideas and the numbers in your calculations. How many possible ways are there to order one row? Thanks. $\endgroup$ – lameK Nov 4 '14 at 14:47
  • $\begingroup$ @lameK, that's right. There are 3344 ways to order one row. $\endgroup$ – Peter Taylor Nov 4 '14 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.