Determining number of possible move sequences in Connect-4

[NickBach]

There's a game that's been around for a long time called Connect 4. It is a 2-player game consisting of 7 columns that can hold 6 discs each. The players alternate dropping a disc of their color into one of the 7 columns until a player has 4 in a row, either horizontally, vertically, or in a diagonol (or until all 42 spots are filled in without a 4-in-a-row sequence resulting that is a tie). I'm trying to determine how many different possible sequences of moves can be made to fill in the remaining spots (assuming a tie will result) at any point during the game. For example, assume the 7 colums already have 2, 1, 6, 4, 5, 0, 2 discs in them (a total of 20), how many ways can the last 22 positions be filled in? Remember, all 22 remaining spots cannot be selected for the next move, only the next one up in each column that currently has less than 6 discs in them. And also, if player A drops 2 discs into the 1st column while player B drops 1 disc into the 4th and then the 5th columns, it should be considered a different sequence than if player B first dropped a disc into the 5th column followed by a disc into the 4th column on this second turn.

Thanks,
Nick

 

[awkward]

There's a game that's been around for a long time called Connect 4. It is a 2-player game consisting of 7 columns that can hold 6 discs each. The players alternate dropping a disc of their color into one of the 7 columns until a player has 4 in a row, either horizontally, vertically, or in a diagonol (or until all 42 spots are filled in without a 4-in-a-row sequence resulting that is a tie). I'm trying to determine how many different possible sequences of moves can be made to fill in the remaining spots (assuming a tie will result) at any point during the game. For example, assume the 7 colums already have 2, 1, 6, 4, 5, 0, 2 discs in them (a total of 20), how many ways can the last 22 positions be filled in? Remember, all 22 remaining spots cannot be selected for the next move, only the next one up in each column that currently has less than 6 discs in them. And also, if player A drops 2 discs into the 1st column while player B drops 1 disc into the 4th and then the 5th columns, it should be considered a different sequence than if player B first dropped a disc into the 5th column followed by a disc into the 4th column on this second turn.

Thanks,
Nick

Hi Nick,

If I understand you correctly, the players are to continue taking turns until all 42 spots are filled, is that right? If so, I think there are
[tex]\frac{42!}{(6!)^7}[/tex]
possible games.

To see this, lay out 42 disks in a row and mark each disk with a number from 1 to 7, using each number exactly 6 times. This can be done in
[tex]\binom{42}{6 \; 6 \; 6 \; 6 \; 6 \; 6 \; 6}[/tex]
ways (a multinomial coefficient). http://en.wikipedia.org/wiki/Multinomial_coefficient

Have the players take turns picking up a disk, working from left to right, color it with the appropriate color for the player, and drop it in the column matching the mark on the disk.

Finally,
[tex]\binom{42}{6 \; 6 \; 6 \; 6 \; 6 \; 6 \; 6}= \frac{42!}{(6!)^7}[/tex]

 

[NickBach]

awkward,

Sounds so simple the way you explain it. Thanks for the reply (and the informative link). I'm trying to write a program to play the game and sometimes the computer seems to be hung while thinking about its move. I want to put in a status of how far along it is in generating its move, but was struggling to come up with the formula to use.

Thanks,
Nick