我有一个包含81个顶点（每个顶点是顶点类的实例）一个很好的曲线图（列表）。 每个顶点有20个邻居。 每个顶点具有多个可能值（从1到9）其中，由于一些初始约束该问题将在平均4或5。我实现了一个简单的DFS在这个曲线图中，其采取的节点具有较少可能的值，的foreach值建立仅具有可能值的彼此“deepcopied”图形，最后再次通入DFS的“deepcopied”图表递归。 这个问题是关于速度; cProfiling我的代码，我发现该641秒我的Mac需要解决这个问题的635是由copy.deepcopy使用。 是否有此问题的任何变通办法？ 这里是我的DFS：
def dfs(graph):
global initial_time_counter
if all(len(i.possible_values)==1 for i in graph):
sys.exit("Done in: %s" % (time.time()-initial_time_counter))
#find out the non-solved vertex with minimum possible values
min_vertex=sorted(filter(lambda x: len(x.possible_values)>1,graph),
key=lambda x: len(x.possible_values))[0]
for value in min_vertex.possible_values:
sorted_graph_copy=sorted(copy.deepcopy(graph), key=lambda x: len(x.possible_values))
min_vertex_copy=filter(lambda x: len(x.possible_values)>1,sorted_graph_copy)[0]
sorted_graph_copy.remove(min_vertex_copy)
if min_vertex_copy.try_value(value): #Can this vertex accept value -> value?
min_vertex_copy.set_value(value) #Yes, set it.
sorted_graph_copy.append(min_vertex_copy) #Append it to the graph.
dfs(sorted_graph_copy) #Run the DFS again.
return False
PS为最聪明的你可能已经意识到这个问题通常被称为数独。 请注意，我不是在寻找特定的数独的答案，以抽象的方式来分析这个问题。
[编辑]
同样的问题，用顶点的纯字符串表示走近，就把<0.75秒来解决。 我张贴供参考整个代码，如果任何人经历在今后类似的问题：
import sys,time
def srange():
return [[x,y] for x in range(9) for y in range(9)]
def represent_sudoku(sudoku):
print "\n".join(["|".join([str(elem) for elem in line]) for line in sudoku])
#Hard sudoku
sudoku=[[4, 0, 0, 0, 0, 0, 8, 0, 5], [0, 3, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 6, 0], [0, 0, 0, 0, 8, 0, 4, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 7, 0], [5, 0, 0, 2, 0, 0, 0, 0, 0], [1, 0, 4, 0, 0, 0, 0, 0, 0]]
represent_sudoku(sudoku)
def get_nbs(x,y,sudoku,also_incomplete=False):
line_nbs=sum([elem for elem in sudoku[y] if ((elem!=[0] and len(elem)==1) or also_incomplete)],[])
column_nbs=sum([sudoku[xline][x] for xline in range(9) if ((sudoku[xline][x]!=[0] and len(sudoku[xline][x])==1) or also_incomplete)],[])
area_nbs=[[j for j in i[(x/3)*3:(x/3)*3+3] if ((j!=[0] and len(j)==1) or also_incomplete)] for i in sudoku[(y/3)*3:(y/3)*3+3]]
area_nbs=sum(sum(area_nbs,[]),[])
if not also_incomplete:
return list(set(line_nbs+column_nbs+area_nbs))
return line_nbs+column_nbs+area_nbs
for x,y in srange():
sudoku[y][x]=[sudoku[y][x]]
def base_cleanup(sudoku):
while 1:
something_changed=False
for x,y in srange():
if sudoku[y][x]==[0] or len(sudoku[y][x])>1:
possible_values=range(1,10) if sudoku[y][x]==[0] else sudoku[y][x]
sudoku[y][x]=list(set(possible_values)-set(get_nbs(x,y,sudoku)))
if sudoku[y][x]==[]:
return False
something_changed=True if possible_values!=sudoku[y][x] else False
else:
sudoku[y][x]=sudoku[y][x]
if not something_changed:
break
return sudoku
def dfs(graph):
global s
if graph==False:
return False
if all(sum([[len(elem)==1 for elem in line] for line in graph],[])):
represent_sudoku(graph)
sys.exit("Done in: %s" % (time.time()-s))
enumerated_filtered_sudoku=filter(lambda x: len(x[1])>1, enumerate(sum(graph,[])))
sorted_enumerated_sudoku=sorted(enumerated_filtered_sudoku,key=lambda x: len(x[1]))
min_vertex=sorted_enumerated_sudoku[0]
possible_values=[value for value in min_vertex[1]]
for value in possible_values:
graph_copy=[[elem for elem in line] for line in graph]
y,x=elements_position[min_vertex[0]]
if not any(value==i for i in get_nbs(x,y,graph_copy)):
graph_copy[y][x]=[value]
if base_cleanup(graph_copy)!=False:
graph_copy=base_cleanup(graph_copy)
if graph_copy:
dfs(graph_copy)
return False
sudoku = base_cleanup(sudoku)
elements_position = {i:srange()[i] for i in range(81)}
s = time.time()
dfs(sudoku)
