81個の頂点を含む素敵なグラフ（リスト）があります（各頂点はVertexクラスのインスタンスです）。各頂点には20個の隣接があります。各頂点にはいくつかの可能な値（1から9の範囲）があり、問題に対するいくつかの初期制約を考えると、平均して4または5になります。このグラフに単純なDFSを実装しました。これにより、可能な値が少ないノードが取得されます。 foreach値は、可能な値の1つだけを持つ別の「deepcopied」グラフを作成し、最後に「deepcopied」グラフを再びDFSに再帰的に渡します。問題は速度です。cコードのプロファイリングMacがこの問題を解決するためにかかる641秒のうち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)