Calculating sequential move order from position matrix for Connect4 puzzle

Question

I wanted to know weather we can calculate the move order for a given Connect4 board, such that if the moves are played out sequentially from an empty board, we get the current position on board.

Example:

I have this position matrix for the above pictured board state:

board = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 2, 0, 0],
    [0, 0, 1, 0, 1, 0, 0],
    [0, 0, 2, 1, 2, 0, 0],
] 

So I know the coordinates of the coins from this picture:

• row 1 col 3 = yellow
• row 1 col 4 = red
• row 1 col 5 = yellow
• row 2 col 3 = red
• row 2 col 5 = red
• row 3 col 5 = yellow

In this scenario, the move order (columns) played was: 4, 3, 3, 5, 5, 5:

Red and yellow moves alternate. The numbers represent which columns the coins were dropped, i.e., the first coin (red) was dropped in the 4^th column, the second coin (yellow) was dropped in the 3^rd column, the third coin (red) was dropped again in the 3^rd column...

I wanted to know whether we can reconstruct the move order from the position matrix. The move order does not need not be the exact order that was played, but if we were to simulate it, the resulting position matrix should be the same.

I tried separating the red moves and yellow moves, and created the list of positions for both sets starting from the bottom layer.

# (y,x cordinates ) based on image

red  = [ (1,4), (2,3), (2,5) ] 
yellow = [ (1,3), (1,5), (3,5) ] 

# resulting sequences

red = [4,3,5]
yellow = [3,5,5]

interlaced = [4,3,3,5,5,5]

#sequence : 433555 

And I tried interlacing the column values from these lists, but it doesn't seem to always work: it sometimes messes up the 2^nd red disc as it assumes a yellow disc had already been placed there instead of another column that was played first.

Is there any way to generate a sequence of alternating moves as I mentioned above, if simulated, always get the same matrix of game position?

Answer 1

You could loop over the moves:

• note that a "move" is a column to drop the next token
• tracking the number of tokens already dropped per column
• tracking whose move it is, alternating red or yellow
• check if the position to drop the token corresponds to one of the positions of the current player

The board matrix was edited into the question after my original answer (see further down). Using the board, here's one way to implement a function to verify if the sequence of moves is valid:

def are_valid_moves(moves: List[int]) -> bool:
    """
    :param moves: columns of the moves
    :return: will the sequence of moves produce the red and yellow positions
    """
    tokens_per_column = [0] * len(board[0])
    rows = len(board)

    player = 1
    for column in moves:
        row = rows - tokens_per_column[column] - 1
        tokens_per_column[column] += 1
        if board[row][column - 1] != player:
            return False

        # alternate between 1 and 2
        player = 3 - player

    return True


assert are_valid_moves([4, 3, 3, 5, 5, 5]) is True
assert are_valid_moves([4, 3, 5, 3, 5, 5]) is False

Alternatively, given the positions of red and yellow as list of tuples as in the posted example, here's another way to achieve the same:

MAX_COLUMNS = len(board[0])

def are_valid_moves(red: Tuple[int, int], yellow: Tuple[int, int], moves: List[int]) -> bool:
    """
    :param red: 1-based (y, x) positions of red
    :param yellow: 1-based (y, x) positions  of yellow
    :param moves: columns of the moves
    :return: will the sequence of moves produce the red and yellow positions
    """
    red_set = set(red)
    yellow_set = set(yellow)
    tokens_per_column = [0] * MAX_COLUMNS

    current_is_red = True
    for column in moves:
        row = tokens_per_column[column] + 1
        tokens_per_column[column] = row
        if current_is_red:
            if (row, column) not in red_set:
                return False
        else:
            if (row, column) not in yellow_set:
                return False

        current_is_red = not current_is_red

    return True


red = [(1, 4), (2, 3), (2, 5)]
yellow = [(1, 3), (1, 5), (3, 5)]

assert are_valid_moves(red, yellow, [4, 3, 3, 5, 5, 5]) is True
assert are_valid_moves(red, yellow, [4, 3, 5, 3, 5, 5]) is False

Answer 2

I would suggest turning the matrix data structure into stacks -- one stack per column. These stacks contain values 1 or 2, where 1 is a disc of the first player (red in your case), and 2 is a disc of the second player. So for your example board, those stacks could look like this:

[
    [],        # first column is empty
    [],        # second column is empty
    [2, 1],    # yellow, red
    [1],       # red
    [2, 1, 2], # yellow, red, yellow
    [],
    [],
]

Once you have that, you could use a recursive backtracking algorithm that tries to find a path of "take-back" moves, popping discs from the above-mentioned stacks with alternating colors, until all stacks are empty. Once that state is found the series of moves is known and can be returned.

Here is an implementation of both the conversion to stacks and of the backtracking algorithm:

def getstacks(board):
    counts = [0, 0, 0]
    # Convert data structure to stacks -- one stack per column
    stacks = [[] for _ in board[0]]
    for row, values in enumerate(reversed(board)):
        for col, (value, stack) in enumerate(zip(values, stacks)):
            if value:
                # Verify there are no holes
                if len(stack) != row:
                    raise ValueError(f"The disc at {row+1},{col+1} should not be floating above an empty cell")
                stack.append(value)
                counts[value] += 1
    if not (0 <= counts[1] - counts[2] <= 1):
        raise ValueError("Number of discs per player is inconsistent")
    return stacks, 1 + counts[1] - counts[2] 


def searchmoves(stacks, player):
    # Perform a depth first search with backtracking
    for col, stack in enumerate(stacks):
        if stack and stack[-1] == player:
            stack.pop()
            moves = searchmoves(stacks, 3 - player)
            stack.append(player)  # Restore
            if moves is not None:  # Success
                moves.append(col + 1)
                return moves
    if any(stacks):
        return None  # Stuck: backtrack.
    return []  # Success: all discs were removed


def solve(board):
    stacks, nextplayer = getstacks(board)
    return searchmoves(stacks, 3 - nextplayer)

You can run it as follows:

board = [
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0],
    [0,0,0,0,2,0,0],
    [0,0,1,0,1,0,0],
    [0,0,2,1,2,0,0],
] 
print(solve(board))  # [4, 5, 5, 3, 3, 5]

Another example run:

board =  [
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 2, 1, 0, 0],
    [0, 0, 2, 1, 2, 0, 0],
    [0, 2, 1, 2, 2, 1, 0]
]
print(solve(board))  # [6, 5, 3, 5, 5, 4, 4, 4, 4, 4, 5, 3, 4, 2]