问题:我们有一个 5 行 4 列的正方形网格。我们需要使用这些数字来填充网格； 1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40。我们需要以这样一种方式填充网格，即每个水平和垂直的邻居都应该毫无余地地分割其他人。例如，12 和 3 可以是邻居，因为 12 % 3 == 0，但是 5 和 12 可以't。网格 2x2 被指定为 10。

我尝试使用集合列表来解决问题。每组代表每个网格的可能值。当每个集合只有一个元素时，问题就解决了。以下是我用来尝试解决此问题的函数(我添加了整个内容以防万一，但我认为我的问题出在 solve 函数中。)；

class CannotSolveError(Exception):
    pass

def suitable_neighbor(a,b):
    "return True if a and b can be neighbors."
    return (a > b) and (a % b == 0) or (b % a == 0)

def equalize_tables(table1, table2):
    "Make two tables equal, by changing first one in-place"
    for i in range(len(table1)):
        table1[i] = table2[i]


def remove_possibility(table, row, column, value):
    """Remove possibilities that can't be neighbors with value in rowxcolumn grid."""

    index = ((row - 1) * num_cols) + column - 1

    if len(table[index]) == 1:
        return # This is a solved grid, do nothing.

    remaining_possibilities = set(
        filter(lambda x: suitable_neighbor(x, value), table[index])
                                )

    if not remaining_possibilities:
        raise ValueError("Invalid move")

    if len(remaining_possibilities) == 1:
        "Only one possibility remains, try to put it!"
        copy_table = table[:]
        try:
            "Try it on copy"
            put(copy_table, row, column, remaining_possibilities.pop())
        except ValueError:
            "Cannot put, re-raise and do nothing.."
            raise
        else:
            "Putting is successfull, update original table"
            equalize_tables(table, copy_table)
    else:
        table[index] = remaining_possibilities


def put(table, row, column, value):
    """Put a value on a grid, modifies given table. use with care!"""

    index = ((row - 1) * num_cols) + column - 1

    "Is this move possible?"
    if value not in table[index]:
        raise ValueError("Cannot put %d on %dx%d" % (value, row, column))

    "Remove possibilities from left neighbor"
    if column > 1:
        remove_possibility(table, row, column - 1, value)

    "Remove possibilities from right neighbor"
    if column < num_cols:
        remove_possibility(table, row, column + 1, value)

    "Remove possibilities from upper neighbor"
    if row > 1:
        remove_possibility(table, row - 1, column, value)

    "Remove possibilities from lower neighbor"
    if row < num_rows:
        remove_possibility(table, row + 1, column, value)

    "Remove this value from every other set."
    for i in range(num_rows * num_cols):
        if i == index:
            continue

        table[i].discard(value)

    "Put one-item set in place. Have to do this last."
    table[index] = set([value])



def solve(table):
    "Try to solve the table by trying possible values on grids."

    to_try = [(i,len(table[i])) for i in range(num_rows * num_cols) if len(table[i]) > 1]

    "Grid with least remaining possibilities will be tried first."
    to_try.sort(key = lambda x: x[1])

    for index, _ in to_try:
        for value in table[index]:
            row = index / num_cols + 1
            column = index % num_cols + 1
            copy_table = table[:]
            put(copy_table, row, column, value)
            try:
                solve(copy_table)
                equalize_tables(table, copy_table)
                return
            except CannotSolveError:
                continue
            except ValueError:
                continue
    raise CannotSolveError

我觉得这个算法应该可以解决问题。但是我超出了最大递归深度。有什么想法可以解决这个问题，或者我应该如何在 Python 中更好地解决这个问题？

这不是一道作业题。我正在自己研究这个。

最佳答案

为了避免炸毁你的堆栈，一个更稳健的方法是为你的部分解决方案(部分填充板)设计一个编码，并自己实现回溯。与依赖 python 的堆栈相比，这将需要更少的内存。

Google 的 Peter Norvig 撰写了一篇富有启发性的文章，描述了他如何使用此类技术构建高效的回溯 sudoku solver .它使用一种他称之为“约束传播”的技术来限制选项的空间，以便可以通过强力回溯搜索快速找到解决方案(即，无需检查每个可能的数字网格，但仅追求可能仍会导致解决方案的部分网格)。我认为您会发现它非常适用，不仅适用于一般想法，而且适用于具体情况:您的问题，正如您所处理的那样，非常接近数独求解器。

关于python - 如何摆脱最大递归深度错误或更好地解决这个问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12177600/