尝试用3x3矩阵来比较9x9矩阵中的数字

Question

所以我想解决一个问题，这个问题让你比较9x9数独网格中的数字，看看数独游戏是否有一个有效的/可解的数字网格（这意味着数独规则适用于给定的网格）。我基本上解决了这个问题，但最后一部分我还没搞定。我已经知道如何对每一列/每行上的每个元素求和，但我无法完全解决这个问题，直到我能够真正检查每个3x3网格，看看其中是否有重复的数字。这就是我陷入困境的地方，因为我似乎无法得到正确的算法来以3x3的方式迭代矩阵。在

我试图通过使用一系列for循环来完全控制迭代，这些循环增加了特定的索引数，使其沿着矩阵移动。告诉我我做错了什么——或者是否有其他可能的、更优雅的方法来解决这个问题（使用如此多的for循环会使我的代码看起来又长又丑/效率低下）。在

def sudoku(grid):

grid = [[1,3,2,5,4,6,9,8,7], 
        [4,6,5,8,7,9,3,2,1], 
        [7,9,8,2,1,3,6,5,4], 
        [9,2,1,4,3,5,8,7,6], 
        [3,5,4,7,6,8,2,1,9], 
        [6,8,7,1,9,2,5,4,3], 
        [5,7,6,9,8,1,4,3,2], 
        [2,4,3,6,5,7,1,9,8], 
        [8,1,9,3,2,4,7,6,5]]
duplicate = set()
numHolder = 0
for a in range(0,9):
    for b in range(0,9):
        numHolder+=grid[b][a]
    if numHolder!=45:
        return False
    numHolder=0
for b in range(0,9):
    for x in range(0, 9):
        numHolder += grid[b][x]
    if numHolder != 45:
        return False
    numHolder = 0

for b in range(0,3):
    for c in range(0,3):
        if grid[b][c] in duplicate:
            return False
        else:
            duplicate.add(grid[b][c])
duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d][c+3] in duplicate:
            return False
        else:
            duplicate.add(grid[d][c+3])

duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[b][c+6] in duplicate:
            return False
        else:
            duplicate.add(grid[d][c+6])
duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d+3][c] in duplicate:
            return False
        else:
            duplicate.add(grid[d+3][c])

duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d+3][c+3] in duplicate:
            return False
        else:
            duplicate.add(grid[d+3][c+3])
duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d+3][c+6] in duplicate:
            return False
        else:
            duplicate.add(grid[d+3][c+6])
duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d+6][c] in duplicate:
            return False
        else:
            duplicate.add(grid[d+6][c])

duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d+6][c+3] in duplicate:
            return False
        else:
            duplicate.add(grid[d+6][c+3])

duplicate.clear()
for d in range(0,3):
    for e in range(0,3):
        if grid[d+6][c+6] in duplicate:
            return False
        else:
            duplicate.add(grid[d+6][c+6])
return True

Answer 1

如果您希望在纯python中检查数独的所有约束，最好将所有约束生成为可以总结的值列表：

def check_constraints(constraints, target_sum):
    for _constraint in constraints:
        if sum(_constraint) != target_sum:
            return False
    return True

要提取以行列表形式组织的网格的子矩阵，对一组水平范围和一组垂直范围进行嵌套迭代就足够了：

^{pr2}$

这两组范围由函数make_ranges生成：

def make_ranges(h_step, v_step, length):
    return (make_range(h_step, length), make_range(v_step, length))

它为每个方向调用make_range：

def make_range(step, width):
    range_ = []
    _start = 0
    for _end in range(step, width+1, step):
        range_.append((_start, _end))
        _start = _end
    return range_

为了保持算法的灵活性，网格参数被定义为变量：

SUDOKU_WIDTH = 3
SUDOKU_HEIGHT = 3
CONSTRAINT_LEN = SUDOKU_WIDTH * SUDOKU_HEIGHT
CONSTRAINT_SUM = sum(range(CONSTRAINT_LEN + 1))

通用范围集创建为：

row_ranges = make_ranges(CONSTRAINT_LEN, 1, CONSTRAINT_LEN)
col_ranges = make_ranges(1, CONSTRAINT_LEN, CONSTRAINT_LEN)
quad_ranges = make_ranges(SUDOKU_WIDTH, SUDOKU_HEIGHT, CONSTRAINT_LEN)

从网格中提取相应的约束：

rows = get_grid_constraints(GRID, *row_ranges)
cols = get_grid_constraints(GRID, *col_ranges)
quads = get_grid_constraints(GRID, *quad_ranges)

检查CONSTRAINT_SUM：

^{8}$

这允许详细的调试输出来验证算法的正确操作：

dbg_fwid = 11
dbg_sep = '\n                 {1:<{0}s}'.format(dbg_fwid, '')
def dbg_lists(lists):
    return dbg_sep.join((str(_l) for _l in lists))
def sformat(fmt, *args, **kwargs):
    return fmt.format(*args, **kwargs)

print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "CONSTRAINT_SUM", (CONSTRAINT_SUM)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "row_ranges", (row_ranges)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "col_ranges", (col_ranges)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "quad_ranges", (quad_ranges)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "rows", dbg_lists(rows)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "cols", dbg_lists(cols)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "quads", dbg_lists(quads)))
print(sformat("#    "":DBG:    {1:<{0}s}: ]{2!s}[", dbg_fwid, "is_valid", (is_valid)))

这表明：

CONSTRAINT_SUM: ]45[
row_ranges : ]([(0, 9)], [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)])[
col_ranges : ]([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)], [(0, 9)])[
quad_ranges: ]([(0, 3), (3, 6), (6, 9)], [(0, 3), (3, 6), (6, 9)])[
rows       : ][1, 3, 2, 5, 4, 6, 9, 8, 7]
              [4, 6, 5, 8, 7, 9, 3, 2, 1]
              [7, 9, 8, 2, 1, 3, 6, 5, 4]
              [9, 2, 1, 4, 3, 5, 8, 7, 6]
              [3, 5, 4, 7, 6, 8, 2, 1, 9]
              [6, 8, 7, 1, 9, 2, 5, 4, 3]
              [5, 7, 6, 9, 8, 1, 4, 3, 2]
              [2, 4, 3, 6, 5, 7, 1, 9, 8]
              [8, 1, 9, 3, 2, 4, 7, 6, 5][
cols       : ][1, 4, 7, 9, 3, 6, 5, 2, 8]
              [3, 6, 9, 2, 5, 8, 7, 4, 1]
              [2, 5, 8, 1, 4, 7, 6, 3, 9]
              [5, 8, 2, 4, 7, 1, 9, 6, 3]
              [4, 7, 1, 3, 6, 9, 8, 5, 2]
              [6, 9, 3, 5, 8, 2, 1, 7, 4]
              [9, 3, 6, 8, 2, 5, 4, 1, 7]
              [8, 2, 5, 7, 1, 4, 3, 9, 6]
              [7, 1, 4, 6, 9, 3, 2, 8, 5][
quads      : ][1, 3, 2, 4, 6, 5, 7, 9, 8]
              [9, 2, 1, 3, 5, 4, 6, 8, 7]
              [5, 7, 6, 2, 4, 3, 8, 1, 9]
              [5, 4, 6, 8, 7, 9, 2, 1, 3]
              [4, 3, 5, 7, 6, 8, 1, 9, 2]
              [9, 8, 1, 6, 5, 7, 3, 2, 4]
              [9, 8, 7, 3, 2, 1, 6, 5, 4]
              [8, 7, 6, 2, 1, 9, 5, 4, 3]
              [4, 3, 2, 1, 9, 8, 7, 6, 5][
is_valid   : ]True[

Answer 2

您可以从您的9x9获得3x3的列表

mats_3x3x9 = [grid[3*i:3*i+3] for i in range(3)]
mats_9x3x3 = [
    [row_1x9[3*i:3*i+3] for row_1x9 in rows_3x9]
    for i in range(3)
    for rows_3x9 in mats_3x3x9
]

然后你可以检查每个3x3是否包含数字1到9，例如

^{pr2}$

也许你可以用更小的矩阵

import numpy as np
mats_9x3x3 = np.array(grid)
[mats_9x3x3[3*i:3*i+3, 3*j:3*j+3] for i in range(3) for j in range(3)]

然后您可以找到重复的值，如this question，例如

from collections import Counter
for mat_3x3 in mats_9x3x3:
    if [item for item, count in Counter(mat_3x3).iteritems() if count > 1]:
        return False
return True

Answer 3

这很容易在NumPy中解决：

import numpy as np
import skimage

grid = [[1,3,2,5,4,6,9,8,7],
        [4,6,5,8,7,9,3,2,1],
        [7,9,8,2,1,3,6,5,4],
        [9,2,1,4,3,5,8,7,6],
        [3,5,4,7,6,8,2,1,9],
        [6,8,7,1,9,2,5,4,3],
        [5,7,6,9,8,1,4,3,2],
        [2,4,3,6,5,7,1,9,8],
        [8,1,9,3,2,4,7,6,5]]

# Create NumPy array
grid = np.array(grid)
# Cut into 3x3 sublocks, and flatten each subblock
subgrids = skimage.util.view_as_blocks(grid, (3, 3)).reshape(3, 3, -1)

# Sort each subblock then compare each one with [1, 2, ..., 9]. If all are equal, it is a valid subblock
valid_blocks = np.all(np.sort(subgrids, axis=-1) == np.arange(1, 10), axis=-1)
# array([[ True,  True,  True],
#        [ True,  True,  True],
#        [ True,  True,  True]])

# Sort rows, then compare each one
valid_rows = np.all(np.sort(grid, axis=1) == np.arange(1, 10), axis=1)
# array([ True,  True,  True,  True,  True,  True,  True,  True,  True])

# Sort columns, then compare each one
valid_columns = np.all(np.sort(grid, axis=0) == np.arange(1, 10)[:, None], axis=0)
# array([ True,  True,  True,  True,  True,  True,  True,  True,  True])

# Check if all comparisons were all true
all_valid = np.all(valid_blocks) & np.all(valid_rows) & np.all(valid_columns)
# True