所以,我用回溯算法创建了一个数独求解器。一切工作都很有魅力,但与用java编写的完全相同的解决方案相比,解算器确实很慢。python真的那么慢,还是我的代码中有一个我遗漏的主要bug? 代码如下:
rida = 0
veerg = 0
maatriks = []
regioon = True
regioonid = []
abimaatriks = [[],[],[],[],[],[],[],[],[]]
# Loeb failist maatriksi sisse ja teeb temast listide listi.
def looMaatriks(sisendfail, maatriks):
fail = open(sisendfail)
for line in fail:
line = line.strip()
if line != "":
rida = line.split(" ")
for i in range (0, 9):
if rida[i] != "-":
rida[i] = int(rida[i])
else:
rida[i] = 0
maatriks.append(rida)
return maatriks
maatriks = looMaatriks('sisend1.txt', maatriks)
# Loob failist regiooni.
def looRegioon(sisendfail, reg):
fail = open(sisendfail)
for line in fail:
line = line.strip()
if line != "":
rida = line.split(" ")
reg.append(rida)
for i in range(0,9):
rida[i] = int(rida[i])
return reg
regioonid = looRegioon('sisend2.txt', regioonid)
print(regioonid)
# Loob abimaatriksi, kus regioone säilitada.
def looAbiMaatriks(regioon, abimaatriks):
for i in range (0, 9):
for j in range (0, 9):
abi = regioon[i][j]
abimaatriks[abi-1].append((i, j))
looAbiMaatriks(regioonid, abimaatriks)
print(abimaatriks)
# Kontrollib, kas antud ruudukeses on number juba või mitte.
def numberOlemas(maatriks, rida, veerg):
if maatriks[rida][veerg] != 0:
return True
else:
return False
# Kontrollib, kas arv sobib antud ruutu.
def kasSobib(maatriks, rida, veerg, arv):
for i in range (0, 9):
if arv == maatriks[rida][i]:
return False
for i in range (0, 9):
if arv == maatriks[i][veerg]:
return False
if regioon == False:
reaalgus = 3*int(rida/3)
veerualgus = 3*int(veerg/3)
for k in range(reaalgus, reaalgus + 3):
for l in range(veerualgus, veerualgus + 3):
if arv == maatriks[k][l]:
return False
else:
abi = regioonid[rida][veerg]
for i in abimaatriks[abi-1]:
if maatriks[i[0]][i[1]] == arv:
return False
return True
# Prindib maatriksi ilusal kujul välja.
def prindiMaatriks(maatriks):
for i in range (0, 9):
print(maatriks[i])
print("")
# Peafunktsioon, mis lahendab kogu maatriksi rekursiivselt.
def lahendaRuut(maatriks, rida, veerg):
if veerg > 8:
veerg = 0
rida += 1
if rida == 9:
return True
if numberOlemas(maatriks, rida, veerg) == True:
return lahendaRuut(maatriks, rida, veerg+1)
for i in range(1,10):
if kasSobib(maatriks, rida, veerg, i):
maatriks[rida][veerg] = i
if lahendaRuut(maatriks, rida, veerg+1):
return True
else:
maatriks[rida][veerg] = 0
return False
print ("Esialgne maatriks:")
prindiMaatriks(maatriks)
print("Lahendatud maatriks:")
lahendaRuut(maatriks, rida, veerg)
prindiMaatriks(maatriks)
以下是sisend1.txt的输入:
^{pr2}$以下是sisend2.txt的输入:
1 1 1 2 3 3 3 3 3
1 1 1 2 2 2 3 3 3
1 4 4 4 4 2 2 2 3
1 1 4 5 5 5 5 2 2
4 4 4 4 5 6 6 6 6
7 7 5 5 5 5 6 8 8
9 7 7 7 6 6 6 6 8
9 9 9 7 7 7 8 8 8
9 9 9 9 9 7 8 8 8
Input2包含自定义数独的3x3区域。 如果您想不使用区域进行测试,只需在开始处更改regioon=False。 输入1只是一个要填充的空数独。在
使用列表理解和一些内置函数还有改进的余地。在
例如,而不是:
您可以使用列表:
^{pr2}$也消除了一些具有内置函数的for循环,例如
使用地图:
同时删除不必要的for循环。替换:
有:
相关问题 更多 >
编程相关推荐