蟒蛇副本(),但名单似乎被复制
传给我发现这段代码在这里https://brilliant.org/wiki/recursive-backtracking/蟒蛇副本(),但名单似乎被复制
from itertools import *
from copy import copy
def is_distinct(list):
'''Auxiliary function to is_solved
checks if all elements in a list are distinct
(ignores 0s though)
'''
used = []
for i in list:
if i == 0:
continue
if i in used:
return False
used.append(i)
return True
def is_valid(brd):
'''Checks if a 3x3 mini-Sudoku is valid.'''
for i in range(3):
row = [brd[i][0],brd[i][1],brd[i][2]]
if not is_distinct(row):
return False
col = [brd[0][i],brd[1][i],brd[2][i]]
if not is_distinct(col):
return False
return True
def solve(brd , empties = 9):
'''
Solves a mini-Sudoku
brd is the board
empty is the number of empty cells
'''
if empties == 0:
#Base case
return is_valid(brd)
for row,col in product(range(3),repeat=2):
#Run through every cell
cell = brd[row][col]
if cell != 0:
#If its not empty jump
continue
brd2 = copy(brd)
for test in [1,2,3]:
brd2[row][col] = test
if is_valid(brd2) and solve(brd2,empties-1):
return True
#BackTrack
brd2[row][col] = 0
return False
Board = [ [ 0 , 0 , 0 ],
[ 1 , 0 , 0 ],
[ 0 , 3 , 1 ] ]
solve(Board , 9 - 3)
for row in Board:#Prints a solution
print row
它返回正确的结果,这意味着解决了板。
什么我不明白的是,该solved()
递归函数修改的Board
名单,但该函数从不写brd
,只写brd2
,这是一个副本。
但是,当列表打印在最后时,它显示它已被写入。
所以我有点困惑这段代码,我知道python函数通过引用传递列表,但这个例子明确地使用copy()
。我对复制感到困惑,或者错过了一些东西。
copy.copy
作出浅拷贝。你的情况,你有一个列表的列表和浅拷贝只是创建一个新的列表,但所有元素(内部列表)仍引用旧的名单:
>>> a = [[1,2,3], [2,3,1], [3,1,2]]
>>> b = copy(a)
>>> b[0][0] = 100
>>> a
[[100, 2, 3], [2, 3, 1], [3, 1, 2]]
>>> b
[[100, 2, 3], [2, 3, 1], [3, 1, 2]])
在这种情况下,如果你不”它甚至还可以根本不需要复制,例如
brd2 = brd
一般就可以解决这个使用deepcopy
没有回溯或回溯但没有副本。但是将复制和回溯结合起来似乎有点浪费。
谢谢一堆!我用简单的列表而不是列表的列表尝试类似的事情,并且不能得出相同的结论! – jokoon
您正在创建一个浅副本。
浅拷贝就像当你有一个对象,并且它具有对其他对象的引用。
所以,如果你复制主对象,你还没有复制它的内部引用。它仍然指向与之前的主对象相同的对象。
了解更多关于HERE
浅层和深层的复制之间的差别是仅适用于化合物的对象(即包含其他对象的对象,如列表或类实例)有关:
浅复制构造一个新的复合对象,然后(尽可能)将引用插入到原始对象中。
深层副本构造一个新的复合对象,然后递归地将副本插入原始对象中的副本。
的代码永远不会分配给复制列表本身,所以它似乎是完全多余的。 – ekhumoro