7

我正在尝试在 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 个元素（使用 ill_formed 示例，您会看到情况并非如此）。然后我尝试检查每一行中的重复项，但我在这样做时遇到了一些麻烦。我认为我可以遍历每一行并遍历该行中的每个元素，并将 1 添加到整数列表（行出现）中。例如，如果第一个数字是 2，那么 rowoccurence[2] 应该等于 1。零在 rowoccurence[0] 中并且没有被检查（我有一个临时列表，它应该包含除第一个元素之外的所有内容 - 零 - 因为一行中可能有超过 1 个零，并且网格仍然是合法的）。我尝试根据正确值的参考列表检查临时列表（基本上是行出现），但它似乎不起作用。你能帮我检查一下这个数独检查器中的重复行吗？非常感谢您！

4

13 回答 13

13

请记住，您不是在搜索重复项——只是非零重复项。求和一组适用于此。您还可以同时检查行/列的合法性：

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)
于 2013-07-12T02:20:09.430 回答
4

你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。（坏主意，见下面的评论。）

于 2013-07-12T01:06:17.323 回答
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
于 2015-11-14T03:52:46.047 回答
2

参考@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))

PS：由于次数少，无法评论。希望有需要的人能找到：）

于 2021-01-11T04:13:31.083 回答
1

定义一个函数来验证没有重复项，然后您可以使用它来检查行、列和 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
于 2013-07-12T01:11:18.650 回答
1

我认为您的代码崩溃的原因是因为您的缩进。你应该做：

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
于 2013-07-12T01:34:32.733 回答
1 
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)])
于 2020-08-07T17:44:51.830 回答
1 
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
于 2021-01-20T08:47:57.237 回答
0

如果要检查一行是否有重复项，而不是

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

数数：

b = True
for i in range(9):
    grid[i].count(grid[i][j]) > 1:
        b = False
    return b

您的方法不仅仅是重复检查，它还需要注意只有一个数字存在，否则会引发越界异常

于 2013-07-12T01:00:00.333 回答
0 
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:
        if checkrow(grid):
            if checkcol(grid):
                return True
            else:
                return False
        else:
            return False
    else:
        return False
else:
    return False

def checkrow(grid):
    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]
        for q in range(9):
            if temprow[q] == 1 or temprow[q] == 0:
                continue
            else:
                return False
    return True

def checkcol(grid):
    for num in range(9):
        coloccurence = [0,0,0,0,0,0,0,0,0,0]
        for i in range(9):
            coloccurence[grid[i][num]] += 1
        tempcol = coloccurence[1:10]
        for q in range(9):
            if tempcol[q] == 1 or tempcol[q] == 0:
                continue
            else:
                return False
    return True

好的，伙计们，我回来了一个功能来检查有效的行。非常感谢您提供的所有广泛帮助。我对此有点菜鸟，所以我不明白一些答案，但我意识到我回来得太早了。我还意识到，如果一行中有多个零，那么某些数字将不会出现在 rowoccurence/temp 列表中。这就是为什么我必须在 rowoccurence/temp 列表中检查 1 和 0 的原因。我还编写了一个类似的函数来检查列。再次感谢！

于 2013-07-15T16:40:18.550 回答
0

如何检查每一行/列：

sorted(row) == range(1,10)

或者对于 python 3

sorted(row) == list(range(1,10))

我想运行时间主要是通过创建一个新列表（无论你是使用直方图方法还是排序方法），所以 log(n) 的额外因素不应该是明显的

为了检查每一行、每列和每一个子方格，我建议使用提取器方法从矩阵中获取第 n 行、列和子方格（即不要试图将它们全部放在一个方法中）。

例如：

getSubSquare(m, i):
    subrow = (i // 3) * 3
    subcol = (i % 3) * 3
    v = [0] * 9
    for j in range(9):
        subrj = j // 3
        subcj = j % 3
        v[j] = m[subrow + subrj][subcol + subcj]
    return v

getRow(m,i):
   return m[i]

getCol(m,i):
   return [m[j][i] for j in range(9)]
于 2013-07-12T01:28:25.710 回答
0

我在https://github.com/loghmanb/daily-coding-problem上写了代码

from collections import defaultdict

def solution_valid(board)
    #check row and column is distict no or not?!
    rows = defaultdict(int)
    columns = defaultdict(int)
    squares = defaultdict(int)

    for i in range(9):
        rows.clear()
        columns.clear()
        squares.clear()

        for j in range(9):
            if board[i][j] is not None:
                columns[board[i][j]] += 1
                if columns[board[i][j]]>1:
                    return False
            
            if board[j][i] is not None:
                rows[board[j][i]] += 1
                if rows[board[j][i]]>1:
                    return False

            new_j = (i*3 + j%3)%9
            new_i = (i//3)*3 + j//3
            if squares[board[new_i][new_j]] is not None:
                squares[board[new_i][new_j]] += 1
                if squares[board[new_i][new_j]]>1:
                    return False
    return True
于 2019-10-24T10:44:15.747 回答
0

编写了一个简单的类来模拟（完成的）数独板。没有什么棘手的问题，但对于 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
于 2016-02-10T02:44:27.503 回答