A212693 -id:A212693 - cp's OEIS frontend

A013582 Number of positions in game "Connect Four" (played on usual 6-row, 7-column board) after n moves, up to reflection.

1, 4, 25, 121, 568, 2144, 8231, 27473, 92244, 279241, 831581, 2284733, 6118941, 15465573, 37720667, 88273017, 197300906, 429114775, 881951878, 1784140720, 3373100313, 6336692489, 11005448210, 19131647821, 30415473928, 48633111249

Offset: 0

Russ Cox

Sean A. Irvine, Table of n, a(n) for n = 0..42 [a(42) corrected by Sidney Cadot]
John Tromp, John's Connect Four Playground, viewed Jan 23 2014.
Eric Weisstein's World of Mathematics, Connect-Four

Cf. A212693.

Name clarified by Charles R Greathouse IV, Dec 01 2013
a(3)-a(13) corrected by Sean A. Irvine, Aug 09 2018. The corrected values were confirmed by Russ Cox and extended through a(15), Aug 13 2018
a(16)-a(17) from Sean A. Irvine, Aug 15 2018
Remaining terms a(18)-a(42) from Sean A. Irvine, Oct 02 2018
a(42) corrected by Sidney Cadot, Dec 04 2022, after comparing results of an independent solver and confirming with Sean A. Irvine that the previously given value was indeed erroneous.

A090224 Number of possible positions for n discs on a standard 7 X 6 board of Connect-Four.

Original entry on oeis.org

1, 7, 56, 252, 1260, 4620, 18480, 59815, 206780, 605934, 1869840, 5038572, 14164920, 35459424, 91871208, 214864650, 516936420, 1134183050, 2546423880, 5252058812, 11031780760, 21406686756, 42121344720, 76871042612, 141627466344, 242619996500, 417750499600

Offset: 0

Eric W. Weisstein, Nov 24 2003

			a(2) = 2 * binomial(8,2) since there are binomial(8,2) ways to distribute 2 discs over 7 columns and 2 ways to color them black and white. - _John Tromp_, May 24 2012

Alois P. Heinz, Table of n, a(n) for n = 0..42 (copied from the Victor Allis link)
Victor Allis, A Knowledge-Based Approach of Connect-Four--The Game Is Solved: White Wins.
John Tromp, John's Connect Four Playground, viewed Jan 23 2014.
Eric Weisstein's World of Mathematics, Connect-Four
Wikipedia, Connect Four

Cf. A212693 (legal positions after n plies).

A235610 Array read by antidiagonals: T(n,k) = number of possible positions in standard Connect Four play on a board of height n and width k (n>=1, k>=1).

Original entry on oeis.org

2, 3, 5, 4, 18, 13, 5, 58, 116, 35, 6, 179, 869, 741, 96, 7, 537, 6000, 12031, 4688, 267, 8, 1571, 38310, 161029, 158911, 29737, 750, 9, 4587, 235781, 1706255, 3945711, 2087325, 189648, 2118

Offset: 1

N. J. A. Sloane, Jan 23 2014

			The array as given on the Tromp web site:
height
------
8:      9       13343   8424616 1104642469
7:      8       4587    1417322 135385909       14171315454
6:      7       1571    235781  15835683        1044334437      69173028785     4531985219092
5:      6       537     38310   1706255 69763700        2818972642      112829665923
4:      5       179     6000    161029  3945711 94910577        2265792710      54233186631
3:      4       58      869     12031   158911  2087325 27441956        362940958
2:      3       18      116     741     4688    29737   189648  1216721
1:      2       5       13      35      96      267     750     2118
-------------------------------------------------------------------------------
-:      1       2       3       4       5       6       7  <- width

John Tromp, John's Connect Four Playground, viewed Jan 23 2014.

Cf. A212693, A090224, A013582, A235611, A235612.

A364823 Triangle read by rows: T(n,k) = number of possible positions for four connected discs in the game "Connect Four" played on a board with n columns and k rows, 4 <= k <= n.

Original entry on oeis.org

10, 17, 28, 24, 39, 54, 31, 50, 69, 88, 38, 61, 84, 107, 130, 45, 72, 99, 126, 153, 180, 52, 83, 114, 145, 176, 207, 238, 59, 94, 129, 164, 199, 234, 269, 304, 66, 105, 144, 183, 222, 261, 300, 339, 378, 73, 116, 159, 202, 245, 288, 331, 374, 417, 460

Offset: 4

Felix Huber, Aug 09 2023

In the game, all these positions can be reached. The most difficult thing is to connect four discs in the top row in the case of n=k. Here are examples for 4 X 4, 5 X 5 and 6 X 6:
                                             .  b3 b12  b8 b11  .
                      b3  b5  b8 b10  .      .  a3 a12  b7 a11  .
  b2  b4  b8  b7      b2  a5  a8 a10  .      .  b2 b10  a7 a10  .
  a2  a4  a8  b6      a2  b4  b7  b9  .      .  a2  a8  b6  b9  .
  b1  b3  a7  a6      b1  a4  a7  a9  .      .  b1  a6  b5  a9  .
  a1  a3  b5  a5      a1  a3  b6  a6  .      .  a1  b4  a4  a5  .
For n >= 7 any position in the top row can be reached by the following procedure. By repeating the following scheme, a tower of any height up to the second highest row can be built by placing discs alternately:
  b4  b3  a4  a3
  a1  a2  b1  b2
You can also build a separate tower where you are completely free with at least three discs. While one player places his four discs in the top row, the other moves to these reserve squares. Therefore, any position of four connected discs in the top row can be realized. Example 7 X 7:
  .   a   a   a   a   .   .
  .   b   b   a   a   .   .
  .   a   a   b   b   .   .
  .   b   b   a   a   .   .
  .   a   a   b   b   .   b
  .   b   b   a   a   .   b
  .   a   a   b   b   .   b
For vertical positions there are many reserve squares in the other columns, for diagonal and horizontal positions other than in the top row you have additional reserve squares above three of the four discs to connect. For n > k you have further columns with more reserve squares.

			The triangle T(n,k) begins:
  n/k   4     5     6     7     8     9    10 ...
   4:  10
   5:  17    28
   6:  24    39    54
   7:  31    50    69    88
   8:  38    61    84   107   130
   9:  45    72    99   126   153   180
  10:  52    83   114   145   176   207   238
   .
   .
   .

Wikipedia, Connect Four.

Cf. A013582, A090224, A212693, A059193.

A364823 := proc(n) local k; for k from 4 to n do return 4*k*n - 9*k - 9*n + 18; end do; end proc; seq(A364823(n), n = 4 .. 100);

T(n,k) = 4*k*n - 9*k - 9*n + 18, 4 <= k <= n, comprising k*(n-3) = k*n - 3*k horizontal positions, n*(k-3) = k*n - 3*n vertical positions, and 2*(n-3)*(k-3) = 2*k*n - 6*k - 6*n + 18 diagonal positions.

T(n,n) = 4*n^2 - 18*n + 18 = A059193(n-2).

A342329 Number of different games of Connect Four on an (n+1) X n board.

Original entry on oeis.org

2, 90, 356232, 152505051772, 6961765466482521226

Offset: 1

Robin Jehn, Mar 08 2021

There are many more game variations than positions in the game Connect Four since almost all positions can be reached in many different ways. For the regular 7 X 6 board there are 4531985219092 legal positions (see A212693). If we estimate the number of possible games with the formula (0.75*(n+1))^(n*(n+1)-1), i.e., on average the players have 75% free columns to choose from, there are about 3.0*10^29 possible games.

			a(1) = 2: on a 2 X 1 board the first player can insert their first disc in the right or in the left column, the second player has no choice anymore, hence there are two different games. Obviously for the 2 X 1 and 3 X 2 boards, all games will end in a draw.

Wikipedia, Connect Four

Cf. A013582, A090224, A212693.

def next_turn(player): # there are players 0 and 1
    global total, position
    ngames = 0
    for i in range(n+1):
        fill = int(column[i]) # height of column i
        if fill < n: # throw a disc into column i
            position = position + 2 ** (i + (n + 1) * fill + ntimesnplus1 * player) # unique identifier for this position
            if position in games: # half of memory and cpu-time can be saved if you exploit symmetry of positions here
                ngames = ngames + games[position]
            else:
                column[i] = column[i] + 1
                total = total + 1
                if position in setfinalpos: # we have reached a known final position
                    ngames = ngames + 1
                else: # check if the new position is a win or if the board is full
                    if check4win(position, player, fill, i) or total == ntimesnplus1:
                        setfinalpos.add(position)
                        ngames = ngames + 1
                    else:
                        numbergames = next_turn(1 - player)
                        ngames = ngames + numbergames
                column[i] = column[i] - 1
                total = total - 1
            position = position - 2 ** (i + (n + 1) * fill + ntimesnplus1 * player)
    games[position] = ngames
    return ngames

a(5) from Kester Habermann, Mar 09 2021

cp's OEIS Frontend

A013582 Number of positions in game "Connect Four" (played on usual 6-row, 7-column board) after n moves, up to reflection.

Views

Author

Keywords

Links

Crossrefs

Extensions

A090224 Number of possible positions for n discs on a standard 7 X 6 board of Connect-Four.

Views

Author

Keywords

Examples

Links

Crossrefs

A235610 Array read by antidiagonals: T(n,k) = number of possible positions in standard Connect Four play on a board of height n and width k (n>=1, k>=1).

Views

Author

Keywords

Examples

Links

Crossrefs

A364823 Triangle read by rows: T(n,k) = number of possible positions for four connected discs in the game "Connect Four" played on a board with n columns and k rows, 4 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A342329 Number of different games of Connect Four on an (n+1) X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions