图论题笔记（一）：方格填数

graph_nbr={}
graph_num={}

for row in range(3):
    for col in range(4):
        graph_nbr[(row,col)]=[]        
        graph_num[(row,col)]=None
del graph_nbr[(0,0)]
del graph_nbr[(2,3)]
del graph_num[(0,0)]
del graph_num[(2,3)]

connect=[(-1,0),(-1,-1),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

def plus_tp(tp1,tp2):
    return (tp1[0]+tp2[0],tp1[1]+tp2[1])

for x in graph_nbr.keys():
    for ct in connect:
        result_plus=plus_tp(x,ct)
        if result_plus in graph_nbr and result_plus not in graph_nbr[x]:
            graph_nbr[x].append(result_plus)

def dfs(graph_key,n,path,limit=10):
    if n==limit:
        global count
        print(count,graph_num)
        count+=1
    
    if n<limit:
        for j in graph_key:
            if j not in path :
                has_i_prev=False
                for nbr in graph_nbr[j]:
                    if graph_num[nbr]==n-1:
                        has_i_prev=True
                        break
                if not has_i_prev:
                    graph_num[j]=n
                    path.append(j)
                    dfs(graph_key,n+1,path)
                    path.pop()
                    graph_num[j]=None

mark=[]
count=1
dfs(graph_key=graph_num.keys(),n=0,path=mark)