像数独一样,在9 * 9矩阵中检查3 * 3矩阵是否重复

python numpy matrix

252 观看

1回复

43 作者的声誉

在9 * 9矩阵中的每个3 * 3块中检测重复项

我的方法:使用numpy.vsplit和hsplit将9 * 9分成9个3 * 3块,并使用.flat函数展平每个3 * 3块,然后使用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缺乏经验,因此我想寻求一种更有效的方法来完成此工作。

作者: lilpig 的来源 发布者: 2017 年 9 月 15 日

回应 1


3

171499 作者的声誉

决定

设置:假设a是,9x9并且b3x3您要在其中搜索的子矩阵(较小的网格)a

脚步 :

  • 解决这个问题的一种方法将被重塑a4Da4D形状的(3,3,3,3),从而每个窗口将是沿着第二和第四轴线。

  • 我们需要扩展b到,3D以便第一根轴与的第二根轴对齐,第二根轴a4D与的第四根轴对齐a4D

  • 进行比较,这是有效的,由NumPy广播提供,这给了我们一个4D布尔数组。在这两个暗处查找所有匹配项,然后简单地获取匹配索引。

因此,实施-

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

如果由于某些原因看起来凌乱,并且您更喜欢使用built-ins,我们可以使用view_as_blocksfrom 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]])

请注意,这些重塑都是正义的views,因此它们不需要额外的存储空间。尽管通过比较可以创建与形状相同的布尔数组a,但它是一个比int / float数组轻(在Linux系统上轻8倍)的布尔数组,因此内存效率还不错。

作者: Divakar 发布者: 2017 年 9 月 15 日
32x32