Python 检查 9*9 矩阵中的 3*3 矩阵是否重复，如数独

Question

我的做法:使用numpy.vsplit和hsplit将9*9分割成9个3*3 block 并使用 .flat 函数压平每个 3*3 block ，然后使用 set() 检查列表是否包含重复

import numpy as np
def validSolution(board):


    b=np.array(board)
    b=np.vsplit(b,3)
    for n,ar in enumerate(b):
        b[n]=np.hsplit(ar,3)

    for ar in b:
        for arr in ar:
            print(len(set(arr.flat))==len(arr.flat))

validSolution([[5, 3, 4, 6, 7, 8, 9, 1, 2],
               [6, 7, 2, 1, 9, 5, 3, 4, 8],
               [1, 9, 8, 3, 4, 2, 5, 6, 7],
               [8, 5, 9, 7, 6, 1, 4, 2, 3],
               [4, 2, 6, 8, 5, 3, 7, 9, 1],
               [7, 1, 3, 9, 2, 4, 8, 5, 6],
               [9, 6, 1, 5, 3, 7, 2, 8, 4],
               [2, 8, 7, 4, 1, 9, 6, 3, 5],
               [3, 4, 5, 2, 8, 6, 1, 7, 9]])

由于我对 python 和 numpy 缺乏经验，我想询问一种更有效的方法来完成这项工作。

Answer 1

设置:假设 a 是 9x9 网格，b 是 3x3 子矩阵(较小grid)，您正在 a 中搜索。

步骤:

• 解决该问题的一种方法是将 a reshape 为 4D :a4D 形状为 (3,3, 3,3)，因此每个窗口将沿着第二个和第四个轴。

• 我们需要将 b 扩展到 3D，以便第一个轴与 a4D 中的第二个轴对齐，第二个轴与第一个和来自 a4D 的第四个。

• 执行比较，这将是高效的，由 NumPy 广播提供，为我们提供一个 4D bool 数组。沿着这两个暗淡查找所有匹配项并简单地获取匹配索引。

因此，实现 -

np.argwhere((a.reshape(3,3,3,3) == b[:,None]).all((1,3)))

示例运行 -

In [190]: a
Out[190]: 
array([[5, 3, 4, 6, 7, 8, 9, 1, 2],
       [6, 7, 2, 1, 9, 5, 3, 4, 8],
       [1, 9, 8, 3, 4, 2, 5, 6, 7],
       [8, 5, 9, 7, 6, 1, 4, 2, 3],
       [4, 2, 6, 8, 5, 3, 7, 9, 1],
       [7, 1, 3, 9, 2, 4, 8, 5, 6],
       [9, 6, 1, 5, 3, 7, 2, 8, 4],
       [2, 8, 7, 4, 1, 9, 6, 3, 5],
       [3, 4, 5, 2, 8, 6, 1, 7, 9]])

In [196]: b = a[-3:,-6:-3] # (2,1) grid

In [197]: b
Out[197]: 
array([[5, 3, 7],
       [4, 1, 9],
       [2, 8, 6]])

In [198]: np.argwhere((a.reshape(3,3,3,3) == b[:,None]).all((1,3)))
Out[198]: array([[2, 1]])

In [199]: b = a[:3:,:3] # (0,0) grid

In [200]: b
Out[200]: 
array([[5, 3, 4],
       [6, 7, 2],
       [1, 9, 8]])

In [201]: np.argwhere((a.reshape(3,3,3,3) == b[:,None]).all((1,3)))
Out[201]: array([[0, 0]])

如果由于某种原因这看起来很困惑，并且您更喜欢使用内置，我们可以使用 view_as_blocks来自 scikit-image，拥有形状不可知的解决方案 -

In [206]: from skimage.util.shape import view_as_blocks

In [207]: np.argwhere((view_as_blocks(a, b.shape) == b).all((2,3)))
Out[207]: array([[0, 0]])

请注意，这些 reshape 都只是 View ，因此它们不需要额外的内存空间。虽然比较会导致创建一个与 a 形状相同的 bool 数组，但作为一个 bool 数组，它比 int/float 数组轻得多(在 Linux 系统上轻 8 倍)，所以不是内存效率太糟糕了。