问题：我们有一个 5 行 4 列的方形网格。我们需要使用这些数字来填充网格；1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40. 我们需要以这样一种方式填充网格，即每个水平和垂直的邻居都应该无余地分割其他。例如，12and3可以是邻居，因为12 % 3 == 0, 但是5and 12 不能。网格 2x2 是10.
我尝试使用集合列表来解决问题。每个集合代表每个网格的可能值。当每个集合只有一个元素时，问题就解决了。这是我用来尝试解决这个问题的功能（我添加了整个东西以防万一，但我认为我的问题在于解决功能。）；
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 中更好地解决这个问题？
这不是一个家庭作业问题。我正在自己解决这个问题。