破解數(shù)獨——回溯法

''' 1、確保不出現(xiàn)連續(xù)兩次only=2的情況 2、只要做了only=2的試填，就壓入Stack做only=1不壓入棧！！ 3、出現(xiàn)報錯，立刻退棧，再錯再退，直到退回第一次only=2的嘗試疑問：1、退檔是否要退a b A B ans的所有檔？ 退檔的具體操作： 先出棧，上一次only=2的嘗試，將另外一個數(shù)字填入即可（即轉(zhuǎn)化成only=1的情況），別的都不用管 ''' from copy import deepcopy from time import clock start = clock() #f（x）函數(shù)的作用是，輸入一組數(shù)據(jù)，返回1-9間的補(bǔ)集 def f(x):ans = []for i in range(1,10):if i not in x:ans.append(i)return ans#用于檢測是否出現(xiàn)數(shù)字重復(fù)，即報錯 def check(x,b,C):flag = Falsefor i in range(1,10):for j in x:if j.count(i)>1:flag = Truebreakfor i in range(1,10):for j in b:if j.count(i)>1:flag = Truebreakfor i in range(1,10):for m in C:for n in m:if n.count(i)>1:flag = Truebreakif flag==True:return "Error"else:return "True"stack_x = [] stack_a = [] stack_b = [] stack_A = [] stack_B = [] stack_ans = [] stack_M = [] #表示每次做only=2的嘗試是，ans的行列 stack_N = []#數(shù)獨是9*9的二維數(shù)組a，輸入空的用0表示 #先嘗試獲取輸入,x表示最原始的數(shù)獨 x = [[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],]#輸入數(shù)獨 num = 0 while num!=9:line = raw_input()k=-1for i in line:k+=1x[num][k]=int(i)num += 1 change = False #change指針用于指示是否將ans插入'x'while True:#import copy模塊的deepcopy復(fù)制數(shù)組#a數(shù)組共有9行，表示每行已經(jīng)存在的數(shù)字0a = deepcopy(x)#去掉所有的0再次存入afor i in a:while True:if 0 in i:i.remove(0)else:break#b數(shù)組是輸入的置換矩陣，即行列交換b = [[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],]for i in range(9):for j in range(9):b[i][j]=x[j][i]#去掉所有0再次存入bfor i in b:while True:if 0 in i:i.remove(0)else:break#A、B兩個數(shù)組表示a、b的補(bǔ)集，再同C三者求交集便表示可能填的數(shù)字A = [None,None,None,None,None,None,None,None,None] for i in range(9):A[i]=f(a[i])B = [None,None,None,None,None,None,None,None,None]for i in range(9):B[i]=f(b[i])#嘗試解決宮內(nèi)重復(fù)的問題#c數(shù)組是3*3表示每個宮內(nèi)的數(shù)字，去0再存入cc = [[[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None]],[[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None]],[[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None]]]temp = []for i in range(3):for j in range(3):temp.append(x[i][j])for i in range(9):c[0][0][i]=temp[i]temp = []for i in range(3):for j in range(3,6):temp.append(x[i][j])for i in range(9):c[0][1][i]=temp[i]temp = []for i in range(3):for j in range(6,9):temp.append(x[i][j])for i in range(9):c[0][2][i]=temp[i]temp = []for i in range(3,6):for j in range(3):temp.append(x[i][j])for i in range(9):c[1][0][i]=temp[i]temp = []for i in range(3,6):for j in range(3,6):temp.append(x[i][j])for i in range(9):c[1][1][i]=temp[i]temp = []for i in range(3,6):for j in range(6,9):temp.append(x[i][j])for i in range(9):c[1][2][i]=temp[i]temp = []for i in range(6,9):for j in range(3):temp.append(x[i][j])for i in range(9):c[2][0][i]=temp[i]temp = []for i in range(6,9):for j in range(3,6):temp.append(x[i][j])for i in range(9):c[2][1][i]=temp[i]temp = []for i in range(6,9):for j in range(6,9):temp.append(x[i][j])for i in range(9):c[2][2][i]=temp[i]#去掉所有的0重新存入數(shù)組cfor i in c:for j in i:while True:if 0 in j:j.remove(0)else:breakC = deepcopy(c)m=-1 for i in c:m+=1n=-1for j in i:n+=1c[m][n]=f(j)#求交集方法，list( set(a) & set(b) & set(c) )#ans代表每個空可以輸入的數(shù)字ans = [[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None],[None,None,None,None,None,None,None,None,None]]for i in range(9):for j in range(9):if x[i][j]==0:ans[i][j]=list( set(A[i]) & set(B[j]) & set(c[i/3][j/3]))else:ans[i][j]=[]'''change指針為True,說明此處ans會導(dǎo)致連續(xù)兩次的only=2，所以加'x''''if change==True:print 'm,n:',stack_M[-1],stack_N[-1]print 'x:',x[stack_M[-1]][stack_N[-1]]print 'sdsadasdasdasd:',ans[stack_M[-1]][stack_N[-1]]if len(ans[stack_M[-1]][stack_N[-1]])!=0:ans[stack_M[-1]][stack_N[-1]].append('x')change=False'''還要優(yōu)先檢測是否已經(jīng)填了重復(fù)的數(shù)字，這是用ans無法檢測出來的'''if check(x,b,C)=="Error":print "Error exists"#退到上一個二選一的Stack檔，并且換數(shù)字，交換位置即可a = stack_a.pop();b = stack_b.pop();A = stack_A.pop();B = stack_B.pop();M = stack_M.pop();N = stack_N.pop();ans = stack_ans.pop();x = stack_x.pop();ans[M][N].pop()print "after [Error] back stack x:"for i in x:print i'''一定要優(yōu)先檢測ans是否報錯，一旦報錯立刻退檔'''#如果ans中該填空為位置有空集，說明暴力填詞出錯，退檔即可m = -1for i in ans:flag1 = False #flag1檢測是否出現(xiàn)error，一旦出現(xiàn)立刻退檔并且跳出for循環(huán)m += 1n = -1for j in i:n += 1if x[m][n]==0 and ans[m][n]==[]:#在應(yīng)該填空的位置ans為空，就報錯flag1 = Trueprint "line "+str(m),"row "+str(n)+" Error exists!"#報錯后立刻退檔，退回上一個二選一a = stack_a.pop();b = stack_b.pop();A = stack_A.pop();B = stack_B.pop();M = stack_M.pop();N = stack_N.pop();ans = stack_ans.pop();x = stack_x.pop();#退回上一個only=2的情形，就將其自動變成only=1的ans空ans[M][N].pop()#因為試填默認(rèn)試第二個，所以直接pop即可breakif flag1==True:break#only表示只能填唯一數(shù)的空數(shù)#若only=0,則找到only=2的進(jìn)行試填，直至再次出現(xiàn)only=1的情況only = Falsefor i in range(9):for j in range(9):if len(ans[i][j])==1:print "There exists only one condition!"print "only a["+str(i)+"]["+str(j)+"]="+str(ans[i][j][0])only = Trueprint ans[i][j],"!!!!!!!!!"print x[i][j]x[i][j]= ans[i][j][0]'''重點，做暴力試填的點，要做全局變量標(biāo)記，因為可能會退檔!!優(yōu)化：優(yōu)先選擇填完Only=2后能產(chǎn)生Only=1的來優(yōu)先Try,這就需要逐一去試，若不能產(chǎn)生Only=1就退檔，再進(jìn)入for尋找下一個Only=2的'''only2 = Falseif only == False:print "No only=1 exists@@@"flag2 = Falsem = -1for i in ans:m += 1n = -1for j in i:n += 1if len(j)==2:only2=Truestack_a.append(deepcopy(a));stack_b.append(deepcopy(b));stack_A.append(deepcopy(A));stack_B.append(deepcopy(B));stack_M.append(deepcopy(m));stack_N.append(deepcopy(n));stack_ans.append(deepcopy(ans));stack_x.append(deepcopy(x))x[m][n]=ans[m][n][1] if check(x,b,C)=="Error":x[m][n]=0#默認(rèn)試填第二個數(shù)字（反正蒙中概率是50%）flag2 = True #flag2表示是否有only=2的空，有的話立刻試填，并且所有數(shù)據(jù)入棧以作備份breakif flag2==True:break#Check檢測是否還有0未填 Check = []for i in x:for j in i:Check.append(j)if 0 not in Check:#所有空已經(jīng)填完，則跳出程序break#如果能跳出while，那么一定產(chǎn)生了答案（但未必是正確的答案） if check(x,b,C)=="True":print "answer:" for i in x:print i else:print "Sorry I cannot @-@"end = clock() print int(start) print int(end) print end-start

數(shù)獨樣例

簡單測試 600090020 972500803 035407001 000300059 050000010 320008400 500704190 701002584 040010007大師級別 302700009 008000045 004001300 000059000 090030060 000260000 001400200 260000100 400002503專家級 000000020 081006000 000000430 006001098 000000000 007000063 003569207 579200000 000007000世界最難數(shù)獨題 by芬蘭數(shù)學(xué)家 800000000 003600000 070090200 050007000 000045700 000100030 001000068 008500010 090000400

總結(jié)

以上是生活随笔為你收集整理的破解数独——回溯法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。