How many different game situations has connect four?

Question

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.

Answer 1

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)

Answer 2

So I've worked on it, but I'm not really qualified to do so. First I wanted to calculate every possibility like 7 then 49 and then it was complicated to avoid redundancies and I was facing another problem, the fact that after 6 pieces played, there was a possibility of having a full columns. Too hard for me. So I decided to calculate every possible full board of 21 0 and 21 1. I found 538257874440 possibility, but, first of all I wasn't taking in account the wining board. And the fact that it's not possible to have the two first line full of one kind of piece. So I figured I wasn't taking the good path since it was only the full board, useless. Finally I had a good idea. Taking a columns alone with 0 1 and 2, so it made 3^6 possibility then I just had to substract the one with 0 on the right of another number (gravity issue) and it wasn't that difficult : 0000000, 0000001, 0000002, 0000011, 0000012 ,000021 ,0000022 ,0000111 ,0000112, 0000121, 0000122, 0000211, 0000212, 0000221, 0000222 If you don't see a patern, it's 1 then 2 then 4 then 8... , which give us 2^0 + 2^1 ... + 2^6 = 2 ^7 - 1 = 127 possibility for a columns, wich make 127^7 = 532875860165503 possible board. Then I figured there was still the same problem with the two lines at the begining and the wining board. So I gave up.

Answer 3

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