Brute Force Geri Bildirimi ile Python Sudoku Özyineleme Hata

Question

Ev ödevi için bir Sudoku bulmaca çözücü yapıyorum, ancak bazı zorluklarla karşılaşıyorum. Kod şu anda çözümden geçiyor, her ne kadar kolay bulmacalar için ona ulaşıyorsa ve daha zor bulmacalar için, görünürde hiçbir sebepten ötürü birkaç 9'la sıkışıp kalıyor. Bunun için herhangi bir yardım isterim. (check_cell, yerleşimin geçerli olup olmadığını belirler.)

1. Geri izleme, bu kodda doğru bir şekilde uygulandıysa ve değilse, bu nasıl düzeltilebilir?
2. Çözücünün donmasını nasıl engelleyebilirim? Yaklaşık 3 satır çözer ve ardından değerlerin çoğunu 9 saniyeye düşürür.

Bazı kod:

def solve_helper(self, row, col): 
# Try placing a number in each column of current row 
    board = self.the_board 
    if board[row][col] != 0: 
     ????? 
    elif board[row][col] == 0: 
     for i in range(1,10): 
      print("Setting value at i with ") + str (i) + (" located at ") + str(row) + str(col) 
      self.set_cell(row, col, i) 
      self.guesses = self.guesses + 1 
      if self.check_cell(row, col): 
       if self.solve_helper(row, col): return True 
      else: 
       self.set_cell(row, col, 0) 
    else: 
     return self.mover(row,col) 
    return False 

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0) 
    else: 
     print "SOLUTION FOUND" 
     return True 

Answer 1

yaşadığınız sorun sizin özyinelemeli çağrıların bazıları bulunduğunda, bu nedenle çözüm, düzgün sonuçları döndürmediğinden birkaç unutmuş olur olduğunu

Yinelemeli yığının seviyesini artırır. İşte mover yapılan özyinelemeli çağrılara return ekleyerek ihtiyacınız ilk düzeltme, var:

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) # added return 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0)  # here too 
    else: 
     print "SOLUTION FOUND" 
     return True 

Ayrıca önceden çözülmüş hücrelerin üzerinde atlamak için solve_helper fonksiyonunun özel durumda benzer bir şey gerekiyor. fonksiyonunun sonu olmalıdır:

else: 
    return self.mover(row, col) # added return 
return False 

Düzenleme:

Tamam, kodda birkaç sorunları tespit ettik. Bunlardan ikisi çözücü ile mantıksal konulardır ve bir tanesi çözme sırasında garip görünmekten başka gerçek sorunlara neden olmayan bir görüntü sorunudur.

konular:

1. İlk olarak, son kod solve_helper yerine mover çağırmıyor, Kendisine olan sensin. Bu, hareket etmeden önce ekstra işlev çağrısı almasını sağlar (aslında çözücüyü kırmayabileceğini düşünüyorum).
2. İkinci olarak, solve_helper, bir hücreyi 9 olarak ayarlarsa, ancak sonra da (daha sonraki bazı hücreler çözülemedikten sonra) geriye dönük olarak ayarlanırsa, 9 geri adım atmadan önce sıfır değerine sıfırlanmaz.
3. Ve son olarak, görüntü sorunu. Hücreleri 0'a ayarlamak, eski değerlerinin görüntülenmesini durdurmaz. Bu, # 2'deki konuya çok benziyordu (9'luk geri çekildikten sonra geride kaldı) ama aslında sadece kozmetik.

İlk sorunun düzeltilmesi kolaydır. Bunun yerine, bir mover numaralı aramayı solve_helper aramayı değiştirin. Asıl soruda koyduğunuz orijinal kodda var. solve_helper doğrudan arama yanlış sonuç almıyor (solve_helper zaten doldurulmuş hücreyi ikinci kez atlayacağından), ancak yinelemenin her seviyesine gereksiz bir ek işlev çağrısı ekler.

İkinci konu biraz daha karmaşıktır ve burası bazı panolarda sıkışıp kaldığınız yerdir. Yapmanız gereken şey, self.set_cell(row, col, 0)'un şu an içinde bulunduğu else bloğu dışına taşınmasını sağlamaktır. Aslında, isterseniz, bunu gerçekten tam olarak diskin dışına taşıyabilirsiniz (eğer gerçekten isterseniz Geçerli hücrenin çalıştığı hiçbir değerden sonra geri izleme.

for i in range(1,10): 
    print("Setting value ") + str (i) + (" at ") + str(row) + ", " + str(col) 
    self.set_cell(row, col, i) 
    self.guesses = self.guesses + 1 
    if self.check_cell(row, col): 
     if self.mover(row, col): 
      return True 
print "Backtracking" 
self.set_cell(row, col, 0) 
return False 

Son olarak, görüntüleme sorununu sabitleme iki değişiklik gerektirir: İşte bu (aynı zamanda return False deyimi yukarı hareket) döngü için en iyi düzenleme olduğunu düşünüyorum şeydir. İlk olarak, koşullu koşullardan kurtulun set_cell. Ekranı her zaman güncellemek istersiniz. Ardından, update_textfield numaralı telefondan, if bloğunun dışına delete aramayı taşıyın, böylece her zaman gerçekleşir (if altında bırakın). Bu, bir hücreyi sıfıra ayarlamak, önceki değeri siler ama gerçek bir 0 karakteri göstermez (hiçbir şey göstermez).

Bunu yapmalıyım. Kullandığınız algoritmanın hala oldukça yavaş olduğunu unutmayın. a board I found on the internet in a quick Google search çözme 122482 tahminleri ve 5 dakikadan fazla sürdü, ama sonunda işe yaradı. Diğer kartlar (özellikle ilk birkaç açık alanda 8 veya 9 saniye gerektirenler) daha uzun sürebilir.