Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Source: Wikipedia commons, File:Connect_Four.gif

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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)

share|improve this answer
    
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) –  moose 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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