yas*_*sar 6 python algorithm recursion
问题:我们有一个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,但是512不能.网格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中更好地解决这个问题？
这不是一个家庭作业问题.我自己正在研究这个问题.
为了避免炸毁堆栈,更强大的方法是为部分解决方案(部分填充板)设计编码,并自己实现回溯.这将需要比依赖python的堆栈少得多的内存.
谷歌的彼得诺维格写了一篇很有启发性的文章,描述了他如何利用这些技术建立一个有效的回溯数独求解器.它使用一种他称之为"约束传播"的技术来限制选项的空间,这样就可以通过强力回溯搜索快速找到解决方案(也就是说,不检查每个可能的数字网格,但只追求可能仍然存在的部分网格导致解决方案).我认为你会发现它非常适用,不仅适用于一般的想法,也适用于细节:你的问题,正如你已接近它,非常接近数独求解器.
今天是下雨天，所以我写了一个解决方案。如果您愿意，我可以发布，但也许您宁愿自己找到？
这里有一些提示：
你的代码似乎不是以 (2,2) 处的 10 开头
当尝试新值时，您可以将其添加到任何空白处。最好的尝试空间是有很多邻居的空间，因为这样可以让你快速测试和拒绝不良值。
上面假设的，或者说同一件事的不同方式 - 我的搜索超过了值。所以我选择了“下一步”的位置并尝试了那里的每个值。相反的方法是搜索位置（选择“下一个值”并在每个位置使用该值进行搜索），但这效率不高（见上文）。
当回溯和重试时，始终遵循相同的位置模式。例如，(2,2) 是 10，那么 (2,3) 可能是 40，那么您可能会发现没有任何内容适合 (2,4)。所以你回溯并删除 40 并在 (2,3) 处尝试不同的数字。但您尝试的第二个数字（10 之后和 (2,2) 处的某个数字）始终为 (2,3)。如果您不小心这样做，您最终可能会测试许多重复的组合。抱歉，不确定这是否很清楚。基本上 - 选择一条您填充的“路径”，并在搜索和回溯时坚持它。因为选择这条路径是为了最大化邻居的数量（上面的点），所以我一边继续一边构建它，但保留了回溯时使用的路径位置的缓存。通过显示代码更容易解释......
对于表，我使用了数组的数组。复制时我重新使用了未更改的列。这应该减少内存使用（我不知道这是否重要）。
搜索只需要递归 40 次（每个值一次），因此堆栈足够大。
在 python 中进行一个简单的搜索，依次尝试每个值，失败时回溯，在我的笔记本电脑上运行约 4 分钟（假设您使用上面的提示）（不打印稍微修改的版本只需 8 秒）。
我发现有一个 python 函数很有用，给定一个网格和一个位置，它返回yield邻居坐标的列表（好吧，一个生成器，带有 ）。这使得编写其他函数（例如测试一步是否正确的函数）变得更加简单。
无论如何，如果您想要代码或解决方案（我更改了代码以打印所有内容，但只有一个），请询问，我会发布。当然，它也可能有一个错误:o)
解决方案
我对此进行了一些调整，现在它打印出 (2,2)=10 解决方案，然后搜索所有解决方案（仍在为我运行）：
#!/usr/bin/python3
nx, ny = 4, 5
values = [1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40]
# grid[x][y] so it is a list of columns (prints misleadingly!)
grid = [[0 for _ in range(ny)] for _ in range(nx)]
# cache these to avoid re-calculating
xy_moves = {}
debug = False
def neighbours(grid, x, y):
'coordinates of vertical/horizontal neighbours'
for (xx, yy) in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
if xx > -1 and xx < nx and yy > -1 and yy < ny:
yield xx, yy
def filled_neighbours(grid, x, y):
'filter "neighbours" to give only filled cells'
return filter(lambda xy: grid[xy[0]][xy[1]], neighbours(grid, x, y))
def count_neighbours(grid, x, y):
'use this to find most-constrained location'
return sum(1 for _ in filled_neighbours(grid, x, y))
def next_xy(grid, depth):
'''given a certain depth in the search, where should we move next?
choose a place with lots of neighbours so that we have good
constraints (and so can reject bad moves)'''
if depth not in xy_moves:
best, x, y = 0, nx // 2, ny // 2 # default to centre
for xx in range(nx):
for yy in range(ny):
if not grid[xx][yy]:
count = count_neighbours(grid, xx, yy)
if count > best:
best, x, y = count, xx, yy
xy_moves[depth] = (x, y)
if debug: print('next move for %d is %d,%d' % (depth, x, y))
return xy_moves[depth]
def drop_value(value, values):
'remove value from the values'
return [v for v in values if v != value]
def copy_grid(grid, x, y, value):
'copy grid, replacing the value at x,y'
return [[value if j == y else grid[i][j] for j in range(ny)]
if x == i else grid[i]
for i in range(nx)]
def move_ok(grid, x, y, value):
'are all neighbours multiples?'
for (xx, yy) in filled_neighbours(grid, x, y):
g = grid[xx][yy]
if (g > value and g % value) or (g < value and value % g):
if debug:
print('fail: %d at %d,%d in %s' % (value, x, y, grid))
return False
return True
def search(grid, values, depth=0):
'search over all values, backtracking on failure'
if values:
(x, y) = next_xy(grid, depth)
for value in values:
if move_ok(grid, x, y, value):
if debug: print('add %d to %d,%d' % (value, x, y))
for result in search(copy_grid(grid, x, y, value),
drop_value(value, values),
depth+1):
yield result
else:
yield grid
# run the search, knowing that (2,2) (which is (1,1) for zero-indexing)
# has the value 10.
for result in search(copy_grid(grid, 1, 1, 10), drop_value(10, values)):
print(result)
# how many solutions in total?
#xy_moves = {} # reset cache
#for (n, solution) in enumerate(search(grid, values)):
# print('%d: %s' % (n, solution))
它首先选择将使用 来添加下一个数字的正方形next_xy()。它会选择尽可能靠近现有数字的位置，以便可以有效地测试和拒绝数字（该位置被保存，xy_moves以便在回溯时不需要重新找到）。对于每个值，它都会使用 来检查将该值放在该位置是否有效move_ok。如果是这样，它会计算一个新的网格（添加了值）和一个新的值列表（删除了使用的值）并递归。当没有可添加的值时，递归结束。
这是结果（每个内部列表都是一列）：
> time ./grid.py
[[4, 20, 5, 35, 7], [40, 10, 30, 1, 21], [8, 2, 6, 18, 3], [24, 12, 36, 9, 27]]
real 0m5.909s
[删除有关递归和生成器的错误评论]
更新
它完成了全局搜索 - 如果您在开始时不修复 (2,2)，则似乎总共有 12 个解决方案（如果您忽略简单的对称性，则有 3 个不同的解决方案）。
更新2
| 归档时间： |
|
| 查看次数： |
2113 次 |
| 最近记录： |