# Determining number of possible move sequences in Connect-4

• NickBach
In summary, if there are 42 disks in a row and each disk has a number from 1 to 7, then there are \frac{42!}{(6!)^7}ways to mark the disks and do the game.
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

NickBach said:
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
$$\frac{42!}{(6!)^7}$$
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
$$\binom{42}{6 \; 6 \; 6 \; 6 \; 6 \; 6 \; 6}$$
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,
$$\binom{42}{6 \; 6 \; 6 \; 6 \; 6 \; 6 \; 6}= \frac{42!}{(6!)^7}$$

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

## 1. How many possible move sequences are there in a game of Connect-4?

There are approximately 4.5 trillion possible move sequences in a game of Connect-4.

## 2. How is the number of possible move sequences calculated?

The number of possible move sequences is calculated by multiplying the number of possible moves at each turn, starting from the first player's first move and ending with the last player's last move. In Connect-4, there are 7 possible moves at each turn, and the average game lasts 42 moves.

## 3. Is it possible for two different games of Connect-4 to have the same move sequence?

Yes, it is possible for two different games of Connect-4 to have the same move sequence. This is because there are certain strategies and patterns that players can follow, resulting in the same sequence of moves.

## 4. How long would it take to play all possible move sequences in Connect-4?

If each game of Connect-4 lasts an average of 10 minutes, it would take approximately 64 million years to play all possible move sequences.

## 5. Can the number of possible move sequences in Connect-4 be reduced?

No, the number of possible move sequences in Connect-4 cannot be reduced. The game is designed to have a large number of possible sequences in order to make it challenging and strategic.

Replies
7
Views
2K
Replies
29
Views
1K
Replies
15
Views
2K
Replies
6
Views
2K
Replies
2
Views
1K
Replies
1
Views
970
Replies
10
Views
1K
Replies
1
Views
564
Replies
6
Views
2K
Replies
4
Views
1K