# How many different game situations has connect four?

In the game connect four with a $7 \times 6$ grid like in the image below, how many game situations can occur?

Rules:

Connect Four [...] is a two-player game in which the players first choose a color and then take turns dropping colored discs from the top into a seven-column, six-row vertically-suspended grid. The pieces fall straight down, occupying the next available space within the column. The object of the game is to connect four of one's own discs of the same color next to each other vertically, horizontally, or diagonally before your opponent.

Source: Wikipedia

Image source: http://commons.wikimedia.org/wiki/File:Connect_Four.gif

Lower bound:

$7 \cdot 6 = 42$, as it is possible to make the grid full without winning

Upper bound:

Every field of the grid can have three states: Empty, red or yellow disc. Hence, we can have $3^{7 \cdot 6} = 3^{42} = 109418989131512359209 < 1.1 \cdot 10^{20}$ game situations at maximum.

There are not that much less than that, because you can't have four yellows in a row at the bottom, which makes $3^{7 \cdot 6 - 4} = 1350851717672992089$ situations impossible. This means a better upper bound is $108068137413839367120$

How many situations are there?

I think it might be possible to calculate this with the approach to subtract all impossible combinations. So I could try to find all possible combinations to place four in a row / column / vertically. But I guess there would be many combinations more than once.

The number of possible Connect-Four game situations after $n$ plies ($n$ turns) is tabulated at OEISA212693. The total is 4531985219092. More in-depth explanation can be found at the links provided by the OEIS site. (E.g. John's Connect Four Playground)

• John's Connect Four Playground didn't provide much more information. He seems to compute all possible games, but I can't see how he did this. Additionally, he mentions a paper which states that there were 70728639995483 situations in total (appendix C) – Martin Thoma Feb 12 '13 at 12:17
• That paper by Victor Allis did not calculate the exact number, but rather provided 70728639995483 as a upper bound. See page 10 of 91: "In the calculations we are going to make, we do not rule out positions in which are illegal for the reason mentioned above." – Ivan Loh Feb 12 '13 at 12:34
• Also see tzi.de/~edelkamp/publications/conf/ki/EdelkampK08-1.pdf and if you understand German, tzi.de/~edelkamp/lectures/ae/slide/AE-SymbolischeSuche.pdf might be useful as well. – Ivan Loh Feb 12 '13 at 12:43
• @IvanLoh links are dead – Jan Sep 21 '18 at 9:29

I think that:

"Every field of the grid can have three states: Empty, red or yellow disc. Hence, we can have (...) game situations at maximum."

is not correct.

The reason is that by just capturing that each cell can have 3 states, we´re allowing "floating" discs in the board, and the game rules (and physics :) restrict the discs to be stacked.

That is, the "empty" state must be always "filling" any number of discs in the column, and every disk must reside upon another disk, besides the zero row.

So, the "Upper Bound" as defined is lower by a good chunk (https://oeis.org/A212693/b212693.txt seems to be like a good answer)...