问数独解递归解
EN

Code Review用户

提问于 2017-02-20 17:00:50

回答 2查看 2.5K关注 0票数 8

下面是我在Python2.7中为数独解析器编写的代码。任何关于性能改进、代码错误或一般代码风格建议的建议都将受到欢迎。

我的主要想法是：

使用方法生成一些随机数据，然后使用check_invalid查看它是否是有效的Sudoku。
如果从1开始，它是一个有效的Sudoku，那么我将调用resolve_sudoku来填充有效值。

我发现我的代码有时运行很长时间而没有完成。你能找到什么代码错误吗？

import random
from collections import defaultdict
found = False
def check_invalid(matrix):
    # check for each row
    for row in range(len(matrix)):
        cur_row = set()
        for col in range(len(matrix[0])):
            if matrix[row][col] == 0:
                continue
            elif 1 <= matrix[row][col] <= 9:
                if matrix[row][col] in cur_row:
                    return False
                else:
                    cur_row.add(matrix[row][col])
            else:
                return False # invalid number
    # check each col
    for col in range(len(matrix[0])):
        cur_col = set()
        for row in range(len(matrix)):
            if matrix[row][col] == 0:
                continue
            elif 1 <= matrix[row][col] <= 9:
                if matrix[row][col] in cur_col:
                    return False
                else:
                    cur_col.add(matrix[row][col])
            else:
                return False # invalid number
    # check each 3*3 square
    for start_row in [0,3,6]:
        for start_col in [0,3,6]:
            cur_square = set()
            for row in range(start_row, start_row+3):
                for col in range(start_col, start_col + 3):
                    if matrix[row][col] == 0:
                        continue
                    elif 1 <= matrix[row][col] <= 9:
                        if matrix[row][col] not in cur_square:
                            cur_square.add(matrix[row][col])
                        else:
                            return False
                    else:
                        return False # invalid value
    return True

def resolve_sudoku(matrix, row_map, col_map, square_map, cur_row, cur_col):
    global found
    if found:
        return
    if cur_row == len(matrix):
        found = True
        for r in matrix:
            print r
    elif cur_col == len(matrix[0]):
        resolve_sudoku(matrix, row_map, col_map, square_map, cur_row+1, 0)
    elif matrix[cur_row][cur_col] != 0:
        resolve_sudoku(matrix, row_map, col_map, square_map, cur_row, cur_col+1)
    else:
        for val in range(1,10):
            square_x = cur_row / 3
            square_y = cur_col / 3
            if val in row_map[cur_row] or val in col_map[cur_col] or val in square_map[(square_x, square_y)]:
                continue
            else:
                row_map[cur_row].add(val)
                col_map[cur_col].add(val)
                square_map[(square_x, square_y)].add(val)
                matrix[cur_row][cur_col] = val
                resolve_sudoku(matrix, row_map, col_map, square_map, cur_row, cur_col+1)
                row_map[cur_row].remove(val)
                col_map[cur_col].remove(val)
                square_map[(square_x, square_y)].remove(val)
                matrix[cur_row][cur_col] = 0
                if found:
                    return
if __name__ == "__main__":
    matrix = []
    for row in range(9):
        cur_row = []
        for col in range(9):
            if random.random() < 0.1:
                cur_row.append(random.randint(1,9))
            else:
                cur_row.append(0)
        matrix.append(cur_row)
    for r in matrix:
        print r
    re = check_invalid(matrix)
    print re
    if re:
        # init for row map and col map
        row_map = defaultdict(set)
        col_map = defaultdict(set)
        square_map = defaultdict(set)
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                square_x = row / 3
                square_y = row / 3
                if matrix[row][col] != 0:
                    row_map[row].add(matrix[row][col])
                    col_map[col].add(matrix[row][col])
                    square_map[(row, col)].add(matrix[row][col])
        resolve_sudoku(matrix, row_map, col_map, square_map, 0, 0)

python

algorithm

python-2.x

sudoku

回答 2

Code Review用户

回答已采纳

发布于 2017-03-04 21:24:59

让我们把它一片片地拆开。

生成矩阵

首先，将“生成潜在sudoku矩阵”移动到一个单独的函数中。而且，我们可以通过使用清单理解来改进它：

def generate_sudoku_matrix():
    """Generates a 9x9 matrix with random numbers from 1 to 9, leaving 0s as unsolved."""
    return [[0 if random.random() < 0.1 else random.randint(1, 9)
             for _ in range(9)]
            for _ in range(9)]

注意_用于丢弃变量的使用。

验证矩阵

首先，我将调用函数check_valid()而不是check_invalid()，因为在矩阵有效的情况下，您将返回True。不过，更好的名称可能是类似于is_valid_sudoku()。

该函数本身过于复杂，而且也违反了干原理，因为您基本上对行、列和3x3平方重复相同的检查。

如果我们定义一个可重用的函数来验证一个“块”(行、列或正方形)，该怎么办：

def is_valid_block(block):
    """Returns true if a block (row, column or square) is a valid Sudoku block."""
    return len(block) == 9 and sum(block) == sum(set(block))

并将其应用于以下3种情况：

from itertools import chain


def is_valid_sudoku(matrix):
    """Returns True if a Sudoku matrix is valid, False otherwise."""

    # check each row
    for row in matrix:
        if not is_valid_block(row):
            return False

    # check each column
    for col in zip(*matrix):
        if not is_valid_block(col):
            return False

    # check each 3x3 square
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            square = list(chain(row[j:j + 3] for row in matrix[i:i + 3]))
            if not is_valid_block(square):
                return False

    return True

我们还可以更进一步，利用生成器和all()：

def generate_blocks(matrix):
    """Generates rows, columns and 3x3 squares for a Sudoku matrix."""
    for row in matrix:
        yield row

    for col in zip(*matrix):
        yield col

    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            yield list(chain(*(row[j:j + 3] for row in matrix[i:i + 3])))


def is_valid_sudoku(matrix):
    """Returns True if a Sudoku matrix is valid, False otherwise."""
    return all(is_valid_block(block) for block in generate_blocks(matrix))

解数独

首先，将初始映射设置移动到单独的函数，以保持"main“函数的干净和可读性。

我不喜欢使用全局found变量处理退出函数的方式。它使得很难跟踪程序的流程，并且损害了模块性和关注点的分离。

另一个需要改进的地方是临时映射和矩阵修改和回滚。不过，我不确定复制数据结构以将其传递给下一个递归调用是否会更干净和更快。

我以前从未编写过sudoku求解器，但下面是我对实现蛮力解决方案的想法(我想这只是一种不同的方法，与代码评审无关)：

定义is_valid_solved_sudoku()函数，该函数将验证一个矩阵是否为有效求解的sudoku矩阵。该函数将与is_valid_sudoku()非常相似，除了检查每个“块”的方式--不再允许使用0。
然后，is_valid_solved_sudoku()正结果将是我们的递归基条件。
然后，在每个递归调用中，我们找到下一个未解决的单元格(带有0值)的位置。
对于每个row_index，0单元格的col_index，从相应的行、列和平方中获取一组不可能的值/排除数字。
对每个数进行递归调用，不包括我们在上一步构造的一组排除数中的数字

代码风格及其他问题和建议：

使用漂亮印刷pprint代替常规打印
脚本“主”部分中未使用的square_x和square_y变量(实际上可能是错误/错误，因为我希望您使用它们为square_map字典创建一个键)
按PEP8 (参考文献)组织导入
函数之间的两行空行(参考文献)

票数 4

Code Review用户

发布于 2017-03-05 01:57:51

至于性能，这并不是因为您的算法(非常高效)，而是其中的几个bug：

def resolve_sudoku(matrix, row_map, col_map, square_map, cur_row, cur_col):
    global found
    if found:
        return
    if cur_row == len(matrix):
        found = True
        for r in matrix:
            print r
    elif cur_col == len(matrix[0]):
        resolve_sudoku(matrix, row_map, col_map, square_map, cur_row+1, 0)
    elif matrix[cur_row][cur_col] != 0:
        resolve_sudoku(matrix, row_map, col_map, square_map, cur_row, cur_col+1)
    else:
        for val in range(1,10):
            # square_x = cur_row / 3 # <- bug
            square_x = cur_col / 3
            # square_y = cur_col / 3 # <- bug
            square_y = cur_row / 3
            if val in row_map[cur_row] or val in col_map[cur_col] or val in square_map[(square_x, square_y)]:
                continue
            else:
                row_map[cur_row].add(val)
                col_map[cur_col].add(val)
                square_map[(square_x, square_y)].add(val)
                matrix[cur_row][cur_col] = val
                resolve_sudoku(matrix, row_map, col_map, square_map, cur_row, cur_col+1)
                row_map[cur_row].remove(val)
                col_map[cur_col].remove(val)
                square_map[(square_x, square_y)].remove(val)
                matrix[cur_row][cur_col] = 0
                if found:
                    return