# 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)