Python судоку решатель медленно

Question

Таким образом, я создал Sudoku Solver с откатами алгоритма. Все работает как шарм, но решатель действительно медленный по сравнению с и идентичным решением, написанным в java. Является ли python действительно медленным, или в моем коде есть большая ошибка, которую мне не хватает? Вот код:

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:

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

- - - - - - - - - 

Вот вход для 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 - это только пустая судоку для заполнения.

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