从 Connect4 拼图的位置矩阵计算顺序-解网

问：

我想知道天气，我们可以计算给定 Connect4 板的移动顺序，这样，如果移动是从空板上按顺序进行的，我们就会得到板上的当前位置。

例：

我有上图板状态的位置矩阵：

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],
]

所以我从这张图片中知道硬币的坐标：

第 1 行 col 3 = 黄色
第 1 行 col 4 = 红色
第 1 行 col 5 = 黄色
第 2 行 col 3 = 红色
第 2 行 col 5 = 红色
第 3 行 col 5 = 黄色

在此方案中，播放的移动顺序（列）为：4、3、3、5、5、5：

红色和黄色交替移动。这些数字代表硬币被丢弃的列，即第一枚硬币（红色）掉落在第 4 列，第二枚硬币（黄色）掉落在第 3 列，第三枚硬币（红色）再次掉落在第^{3 列......}

我想知道我们是否可以从位置矩阵中重建移动顺序。移动顺序不一定是所玩的确切顺序，但如果我们要模拟它，生成的位置矩阵应该是相同的。

我尝试将红色动作和黄色动作分开，并从底层开始为两组创建位置列表。

# (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

我尝试将这些列表中的列值交错，但它似乎并不总是有效：它有时会弄乱第 2^张红色光盘，因为它假设已经放置了一张黄色光盘，而不是先播放的另一列。

有没有办法生成我上面提到的一系列交替动作，如果模拟，总是得到相同的游戏位置矩阵？

Python Java 算法矩阵序列

@Aldert抱歉，对于这个特定的小例子，序列是正确的，当堆叠更多示例时会失败，这个矩阵：[[0,0,0,1,0,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]] 0 表示空白，1 表示红币，2 表示黄币。红色和黄色分别：红色：['3'，'6'，'4'，'5'，'4'，'4'] 黄色：['2'，'4'，'5'，'3'，'5'，'4'，'4']，隔行扫描：326445534554441。这是错误的。

答：

0赞 janos 12/29/2022 #1

您可以循环播放以下动作：

请注意，“move”是用于删除下一个令牌的列
跟踪每列已丢弃的令牌数
跟踪是谁的移动，交替红色或黄色
检查掉落代币的位置是否与当前玩家的位置之一相对应

在我最初回答之后，矩阵被编辑到问题中（见下文）。使用，以下是实现函数以验证移动序列是否有效的一种方法：boardboard

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

或者，给定元组的位置和作为元组列表的位置，如发布示例中所示，这是实现相同目的的另一种方法：redyellow

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

1赞 trincot 12/29/2022 #2

我建议将矩阵数据结构转换为堆栈 - 每列一个堆栈。这些堆栈包含值 1 或 2，其中 1 是第一个玩家的圆盘（在您的例子中为红色），2 是第二个玩家的圆盘。因此，对于您的示例板，这些堆栈可能如下所示：

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

一旦你有了这个，你就可以使用递归回溯算法，试图找到一条“收回”移动的路径，从上述堆栈中弹出带有交替颜色的光盘，直到所有堆栈都是空的。一旦找到该状态，一系列移动是已知的，并且可以返回。

以下是转换为堆栈和回溯算法的实现：

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)

您可以按如下方式运行它：

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]

另一个示例运行：

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]

上一个：使用共享序列存储和访问整数列表的最有效方法（Java）

下一个：如何从中推导出第一个子序列，使其元素之和相等且元素数相同？

从 Connect4 拼图的位置矩阵计算顺序

Calculating sequential move order from position matrix for Connect4 puzzle

评论