cp's OEIS Frontend

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

%I A342329 #20 Mar 28 2021 18:54:17
%S A342329 2,90,356232,152505051772,6961765466482521226
%N A342329 Number of different games of Connect Four on an (n+1) X n board.
%C A342329 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.
%H A342329 Wikipedia, <a href="https://en.wikipedia.org/wiki/Connect_Four">Connect Four</a>
%e A342329 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.
%o A342329 (Python)
%o A342329 def next_turn(player): # there are players 0 and 1
%o A342329     global total, position
%o A342329     ngames = 0
%o A342329     for i in range(n+1):
%o A342329         fill = int(column[i]) # height of column i
%o A342329         if fill < n: # throw a disc into column i
%o A342329             position = position + 2 ** (i + (n + 1) * fill + ntimesnplus1 * player) # unique identifier for this position
%o A342329             if position in games: # half of memory and cpu-time can be saved if you exploit symmetry of positions here
%o A342329                 ngames = ngames + games[position]
%o A342329             else:
%o A342329                 column[i] = column[i] + 1
%o A342329                 total = total + 1
%o A342329                 if position in setfinalpos: # we have reached a known final position
%o A342329                     ngames = ngames + 1
%o A342329                 else: # check if the new position is a win or if the board is full
%o A342329                     if check4win(position, player, fill, i) or total == ntimesnplus1:
%o A342329                         setfinalpos.add(position)
%o A342329                         ngames = ngames + 1
%o A342329                     else:
%o A342329                         numbergames = next_turn(1 - player)
%o A342329                         ngames = ngames + numbergames
%o A342329                 column[i] = column[i] - 1
%o A342329                 total = total - 1
%o A342329             position = position - 2 ** (i + (n + 1) * fill + ntimesnplus1 * player)
%o A342329     games[position] = ngames
%o A342329     return ngames
%Y A342329 Cf. A013582, A090224, A212693.
%K A342329 nonn,more
%O A342329 1,1
%A A342329 _Robin Jehn_, Mar 08 2021
%E A342329 a(5) from _Kester Habermann_, Mar 09 2021