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个列表的列表。其中的0代表用户未填写的数字，它们可以在行、列或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个元素（如例子所示，这不是情况）。我尝试检查每行中的重复项，但是我遇到了一些困难。我认为可以循环遍历每行，并循环遍历该行中的每个元素，并将1添加到一个整数列表（rowoccurence）中。例如，如果第一个数字是2，那么rowoccurence [2] 应该等于1。0在rowoccurence [0] 中，并且未经检查（我有一个临时列表，应该不包含第一个元素-零-因为一行中可能有多个零，但网格仍然可以合法）。我尝试使用参考值列表检查临时列表（基本上是rowoccurence），但似乎不起作用。您能帮助我检查数独检查器中的行是否有重复项吗？非常感谢您的帮助！

- quagpwn

---

我希望我能有我的旧电脑和我在大学本科一年级时写的CS2代码，我曾经做过这件事。 - 2rs2ts

无论如何，Counter都是有用的。 - 2rs2ts

“does not seem to be working”意思是似乎没有起作用。出了什么问题，出错在哪里？你正在尝试哪些样本数据，期望它做什么，但实际上它做了什么？函数easy应该返回True还是False？ - abarnert

如果网格没有完全填满，或者从1到9的数字超过一个，检查器应该失败吗？ - dansalmo

Answer 1

记住，你不是在搜索重复项--仅仅是非零重复项。对于此类情况，对一个集合求和即可。同时，你也可以检查行列的合法性：

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)

- llb

---

对于sudoku_ok -> max(l)+1 == 10 == len(set([0]+l)) 可能更快。 - dansalmo

@dansalmo -- 这是一种快速（虽然对我来说有点混淆）检查数独中一行是否为有效答案的方法，但是 OP 只想知道一行是否尚未失效。也就是说，表示空白的零必须被允许。 - llb

Answer 2

你太早地 return 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。（不好的想法，请参见下面的评论。）

- torek

---

在短暂查看代码后无法确定相关性，但是如果 vec [1:10] 是 [0, 1, 2, 0, 1, 2, 0, 1, 2]，那么 sum(vec[1:10]) 也将是 9。 - Noctis Skytower

@NoctisSkytower：好观点，最好使用类似于“all”或直接测试的东西。 - torek

Answer 3

我发布这篇文章是因为大多数其他解决方案虽然可能非常高效，但几乎无法阅读。对于刚开始学习的新手来说，我相信以下代码非常有帮助且易于理解。希望这能帮助任何想学习如何创建数独检查器的人。

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

- Clever Programmer

---

也许我没有理解，但是按照你的方法，即使相同的两个数字在同一个3x3网格中，数独是否被标记为正确呢？因为你只检查行和列。 - mrk

Answer 4

参考了@llb的答案，但该答案没有检查缺失值或零值。这是我的解决方案，可以处理负数、零和缺失值。

def line_ok(e):
    if len(set(e)) != 9: return False
    for i in range(len(e)):
        if e[i] not in range(1,10): return False
    return True
    
def checker(grid):
    bad_rows = [False for row in grid if not line_ok(row)]
    grid = list(zip(*grid))
    bad_cols = [False for col in grid if not line_ok(col)]
    squares = []
    for i in range(0,9,3):
        for j in range(0,9,3):
            square = list(itertools.chain.from_iterable(row[j:j+3] for row in grid[i:i+3]))
            squares.append(square)
    bad_squares = [False for sq in squares if not line_ok(sq)]
    return not any([bad_rows, bad_cols, bad_squares])

print(checker(sudoku_correct))

提示：由于声望不足，无法发表评论。希望需要的人能找到它 :)

- Vers

Answer 5

import numpy as np

def is_valid(row):
    # checks whether a given set of values forms a valid row in sudoku
    return len(list(filter(lambda val: type(val) == int and 0 < val < 10, set(row))) == 9

def check_sudoku(grid):
    """ Check a sudoku board is correctly completed or not. """
    # checks whether the grid has 9 rows
    if len(grid) != 9:
        return False

    # checks whether the grid has 9 columns
    for i in range(9):
        if len(grid[i]) != 9:
            return False

    # turns grid from list to numpy array
    grid = np.array(grid)

    # checks whether the grid is filled with integers
    if grid.dtype != np.int:
        return False

    for i in range(9):
        # checks for repetition in rows
        if not is_valid(grid[i, :]):
            return False
        # checks for repetition in columns
        if not is_valid(grid[:, i]):
            return False
        # checks for repetition in squares
        if not is_valid(grid[i//3*3:i//3*3+3, j%3*3:j%3*3+3]):
            return False

    # returns true if none of the conditions reached
    return True

- Raghul V

Answer 6

定义一个函数来验证是否存在重复项，然后您可以使用它来检查行、列和3x3网格。如果某些条件不满足，例如行数大于9，则可以通过提前返回来减少嵌套块。仅在函数的最后一步中，如果所有检查都没有失败，则返回true。

from collections import Counter

def check_dups(l):
    counts = Counter()
    for cell in l:
        if cell != 0: counts[cell] += 1
        if cell > 9 or counts[cell] > 1: return False
    return True

def check_sudoku(grid):
    if len(grid) != 9: return False
    if sum(len(row) == 9 for row in grid) != 9: return False
    for row in grid:
        if not check_dups(row): return False
    return True

- perreal

---

为什么不使用 len(set([0]+l)) == len([0]+l) 来检查是否有重复项？ - dansalmo

存在被忽略的零，并且需要检查是否有大于9的数字。 - perreal

all(n in range(1,10) for n in l) 检查是否有任何不正确的内容。 - dansalmo

我认为我的答案对于初学者来说是可以的。另一方面，“all”如何验证没有重复项？ - perreal

但你可以有9个1吗？不好意思，也许我没看到什么微不足道的东西。 - perreal

max(l)+1 == 10 == len(set([0]+l))？ - dansalmo

Answer 7

我认为你的代码崩溃的原因是因为缩进。你应该这样做:

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

与其说：

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

或者使用 Counter:

from collections import Counter

...
    if numsinrow == 9:
        for i in range(9):
            count = Counter(grid[i])
            return False if max(count.values()) > 1 else True

- zhangyangyu

Answer 8

valid_solution= lambda board: not any([sorted(row)!=list(range(1,10)) for row in board]) and not any([sorted(list(col))!=list(range(1,10)) for col in zip(*board)]) and not any([sorted(board[i][j:j+3]+board[i+1][j:j+3]+board[i+2][j:j+3]) !=list(range(1,10)) for i in range(0,9,3) for j in range(0,9,3)])

- jivan patel

Answer 9

编写了一个简单的类来模拟（已完成的）数独棋盘。对于9x9棋盘没有什么复杂的问题，提供了一个简单的解决方案。

class SudokuBoard(object):

    DIGITS = set(range(1, 10))

    def __init__(self, values):
        self.values = values

    def row(self, n):
        return self.values[n]

    def rows(self):
        return self.values

    def cols(self):
        return [self.col(i) for i in xrange(9)]

    def col(self, n):
        return [self.values[i][n] for i in xrange(len(self.values))]

    def groups(self):
        return [self.group(i) for i in xrange(9)]

    def group(self, n):
        start_r = (n / 3) * 3
        start_c = n * 3   % 9
        values = []
        for row in xrange(start_r, start_r + 3):
            for col in xrange(start_c, start_c + 3):
                values.append(self.values[row][col])
        return values

    def is_correct(self):
        for row in self.rows():
            if self.DIGITS - set(row):
                return False
        for col in self.cols():
            if self.DIGITS - set(col):
                return False
        for group in self.groups():
            if self.DIGITS - set(group):
                return False
        return True

- Adam Donahue

Answer 10

问题虽然旧，但我留下了一个新的贡献，为其他像我一样来到这里的人提供帮助。

如果我错了，请纠正我，但我认为解决方案非常简单。不需要检查行、列和网格中的重复项，只需检查行即可。因为如果列或网格中有重复项，则行中也会有重复项。 所以我认为只需要检查行上的0和重复项就足够了：

from collections import Counter
solved = True
for row in board:
    if max(Counter(row).values()) > 1: solved = False
    elif 0 in row: solved = False

- Tiago Pimentel