Python sudoku solver slow

Question

그래서, BackTracking 알고리즘을 사용한 스도쿠 솔버를 만들었습니다. 모든 것은 매력처럼 작동하지만, 솔버는 java에 쓰인 것과 비교해 볼 때 실제로 속도가 느리고 똑같습니다. 파이썬이 정말로 느리거나 코드에서 중요한 버그가 누락되었습니다. 다음 코드의 : 사용자 정의 스도쿠에 대한

이

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 

입력 2는 3 × 3 지역이 포함 sisend2.txt의 입력 여기

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

것 : 여기

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에 대한 입력의 . 영역없이 테스트하려면 regioon = False로 변경하십시오. 입력 1은 채워지는 빈 스도쿠입니다.

Answer 1

목록 내장 및 일부 내장 함수를 사용하여 개선 할 여지가 있습니다. 대신 예를 들어

:

rida = line.split(" ") 
for i in range (0, 9): 
     if rida[i] != "-": 
      rida[i] = int(rida[i]) 
     else: 
      rida[i] = 0 

당신은 지능형리스트를 사용하고 있습니다

는 수행

rida = line.split(" ") 
rida = [int(r) if r != "-" else 0 for r in rida] 

또한 기능 내장, 예를 들어,와 루프에 대한 몇 가지를 제거

for i in range(0,9): 
    rida[i] = int(rida[i]) 

사용지도 :

map(int, rida) 

은 또한 루프 불필요한 제거합니다. 교체 :

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 

으로 :

for i in rage(0, 9): 
    if arv in [maatriks[rida][i], maatriks[i][veerg]]: 
     return False