Python中的数独检查器

Question

我正在尝试在python中创建一个数独检查器：

ill_formed = [[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],  # <---
              [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]]
easy = [[2,9,0,0,0,0,0,7,0],
       [3,0,6,0,0,8,4,0,0],
       [8,0,0,0,4,0,0,0,2],
       [0,2,0,0,3,1,0,0,7],
       [0,0,0,0,8,0,0,0,0],
       [1,0,0,9,5,0,0,6,0],
       [7,0,0,0,9,0,0,0,1],
       [0,0,1,2,0,0,3,0,6],
       [0,3,0,0,0,0,0,5,9]]

我期待这样的输入——一个9个列表的列表。零表示用户尚未填写的数字。它们可以在一行、一列或3x3中多次出现。

def check_sudoku(grid):
if len(grid) == 9:
    numsinrow = 0
    for i in range(9):
        if len(grid[i]) == 9:
            numsinrow += 1
    if numsinrow == 9:
        for i in range(9):
            rowoccurence = [0,0,0,0,0,0,0,0,0,0]
            for j in range(9):
                rowoccurence[grid[i][j]] += 1
                temprow = rowoccurence[1:10]
                if temprow == [1,1,1,1,1,1,1,1,1]:
                    return True
                else:
                    return False
    else:
        return False
else:
    return False

我显然需要检查是否有一个9x9列表（网格），以及每行、每列和3x3小正方形中是否没有重复项。在代码中，我首先检查行数是否正确（应该有9行）。然后我检查每一行中是否有9个元素（在病态示例中，您可以看到情况并非如此）。然后我尝试检查每一行中的重复项，但我在这样做时遇到了一些问题。我想我可以循环每一行，循环该行中的每一个元素，并在int列表中添加1（rowOccurrence）。例如，如果第一个数字是2，则rowoccurence[2]应等于1。零位于rowoccurence[0]中，未被选中（我有一个临时列表，它应该包含除第一个元素（零）之外的所有元素，因为一行中可能有多个零，并且网格可能仍然是合法的）。我试图对照正确值的参考列表检查临时列表（基本上是RowOccurrence），但它似乎不起作用。你能帮我检查一下这个数独棋盘中的重复行吗？提前非常感谢！

Answer 1

我发布这个只是因为大多数其他解决方案几乎不可读，尽管它们可能真的很有效。对于刚开始学习的人来说，我相信下面的代码很有帮助并且非常易读。希望这能帮助任何想要学习如何创建数独检查器的人。

def check_sudoku(grid):
    for row in range(len(grid)):
        for col in range(len(grid)):
            # check value is an int
            if grid[row][col] < 1 or type(grid[row][col]) is not type(1):
                return False
            # check value is within 1 through n.
            # for example a 2x2 grid should not have the value 8 in it
            elif grid[row][col] > len(grid):
                return False
    # check the rows
    for row in grid:
        if sorted(list(set(row))) != sorted(row):
            return False
    # check the cols
    cols = []
    for col in range(len(grid)):
        for row in grid:
            cols += [row[col]]
        # set will get unique values, its converted to list so you can compare
        # it's sorted so the comparison is done correctly.
        if sorted(list(set(cols))) != sorted(cols):
            return False
        cols = []
    # if you get past all the false checks return True
    return True

Answer 2

你过早地返回True，因此你永远无法参加你希望失败的测试：

            if temprow == [1,1,1,1,1,1,1,1,1]:
                return True  # <-- this is the culprit
            else:
                return False

其他注释：确保某个向量的所有元素都等于某个常数的一个简单方法是：

all(i == const for i in vector)

另一个更简单的方法是：如果 vec[1:10]都是1，那么 sum（vec[1:10]）必须是9 （坏主意，见下面的评论。）

Answer 3

请记住，您不是在搜索重复项——只是非零重复项。求和一个集合可以做到这一点。您还可以同时检查行/列的合法性：

def sudoku_ok(line):
    return (len(line) == 9 and sum(line) == sum(set(line)))

def check_sudoku(grid):
    bad_rows = [row for row in grid if not sudoku_ok(row)]
    grid = list(zip(*grid))
    bad_cols = [col for col in grid if not sudoku_ok(col)]
    squares = []
    for i in range(9, step=3):
        for j in range(9, step=3):
          square = list(itertools.chain(row[j:j+3] for row in grid[i:i+3]))
          squares.append(square)
    bad_squares = [square for square in squares if not sudoku_ok(square)]
    return not (bad_rows or bad_cols or bad_squares)