在n维矩阵中寻找所有可能的赢条件或线

Question

我正在尝试实现一个n维的抽搐脚趾问题。为了做到这一点，我想看看是否有球员已经赢了。如果有n维矩阵，是否有检查所有线的方法？

我试过在二维和三维中这样做，但不知道如何算法地找到所有的赢线。我希望下文能更详细地解释这个问题。

因此，如果我们在3x3板上玩2D抽搐脚趾游戏，如下所示：

0 1 2     
3 4 5     
6 7 8

可能的线(tic tac脚趾获胜条件)是:水平和垂直赢：

[0 1 2]     
[3 4 5]     
[6 7 8]     
[0 3 6]     
[1 4 7]     
[2 5 8]

对角线胜利：

[0 4 8]     
[2 4 6]

如果我们在4x4板上进行三维播放，则水平线和垂直线是：

[0 1 2 3]     
[4 5 6 7]     
[ 8  9 10 11]     
[12 13 14 15]     
[ 0  4  8 12]     
[16 20 24 28]     
[32 36 40 44]     
[48 52 56 60]     
[ 0 16 32 48]     
[ 1 17 33 49]     
[ 2 18 34 50]     
[ 3 19 35 51]

还有其他对角线(清单并非详尽无遗)，即：

[0 20 40 60]     
[0 21 42 63]

第一个是一个边缘对角线，它停留在一个切片中，第二个是从角到角。像2，5，8这样的东西也能在4x4板上赢得条件，因为它是一块长3的板子。

是否有一种方法可以在边尺寸n的m维板上找到长度l或更长(水平、垂直和对角线)的所有可能线？N将大于l，m至少等于2。

我目前正在使用以下代码查找所有水平和垂直情况：

def winEvaluation(boardInput):
     dimensions = len(boardInput.shape)

     for i in range(dimensions):
         flatMatrix = np.transpose(boardInput,np.roll(np.arange(dimensions),i)).flatten().reshape(edgeLength**(dimensions-2),edgeLength,edgeLength)
         for array in flatMatrix[0]:
           print(array)`

但是，随着维度的增加，我对如何找到所有的对角线并没有很强的把握。

Answer 1

可能做得很糟糕，但这里有个解决方案。可能可以修改任何axbxcxd。板子大小。

关键的洞见是，可赢性是可传递的:如果A和B、B和C之间有一个获胜序列，那么A和C之间也是如此。

因此，我们使用了不相交的集合结构(这种实现有点内存不足--也许是低效的)，而且每当您有两个端点时，您就使用它们的联合。

from collections import defaultdict

def ticTacToeWins(rowLength, dimensions):
    board = [0]
    wins = DisjSet(rowLength ** dimensions):
    for n in range(dimensions):
        winAdd = (rowLength - 1) * len(board)
        if 0 < n < rowLength:
            for i in range(1, rowLength - 1):
                for s, e in temp:
                    wins.Union(s + i * len(board), e + i * len(board))
        increment = (rowLength ** n)
        for b in board:
            wins.Union(b, winAdd + b)
        temp = wins.unionsSoFar.copy()
        new = []
        for s in range(1, rowLength):
            toAdd = s * increment
            for i in board:
                new.append(i + toAdd)
        board.extend(new)
    return wins.all_wins(rowLength)

# taken from https://www.geeksforgeeks.org/disjoint-set-data-structures/
class DisjSet:
    def __init__(self, n):
        self.rank = [1] * n
        self.parent = [i for i in range(n)]
        self.unionsSoFar = []
 
    def find(self, x):
        if (self.parent[x] != x):
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def Union(self, x, y):
        self.unionsSoFar.append((x, y))
        xset = self.find(x)
        yset = self.find(y)
        if xset == yset:
            return
        if self.rank[xset] < self.rank[yset]:
            self.parent[xset] = yset
        elif self.rank[xset] > self.rank[yset]:
            self.parent[yset] = xset
        else:
            self.parent[yset] = xset
            self.rank[xset] = self.rank[xset] + 1

    def all_wins(self, rowLength):
        sets = defaultdict(list);
        for i, parent in enumerate(self.parent):
            sets[parent].append(i)
        print(sets)
        return [get_win(node1, node2, rowLength) for vals in sets.values() for node2 in vals for node1 in vals  if node1 < node2]
            
def get_win(start, end, rowLength):
    increment = (end - start) // (rowLength - 1)
    return [start + increment * i for i in range(rowLength)]