OFFSET
1,1
COMMENTS
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.
LINKS
Wikipedia, Connect Four
EXAMPLE
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.
PROG
(Python)
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
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Robin Jehn, Mar 08 2021
EXTENSIONS
a(5) from Kester Habermann, Mar 09 2021
STATUS
approved