ब्रूट फोर्स उलटे पांव लौटने त्रुटि

Question

मैं होमवर्क के लिए एक सुडोकू पहेली solver कर रहा हूँ, लेकिन कुछ कठिनाई का सामना कर रहा हूँ के साथ अजगर सुडोकू Recursion। कोड अभी समाधान के पीछे चक्र है, हालांकि यह आसान पहेली के लिए पहुंचता है, और कठिन पहेली के लिए, यह किसी भी स्पष्ट कारण के लिए कई 9 के साथ फंस जाता है। मैं इस पर किसी भी मदद की सराहना करता हूं। (check_cell यह निर्धारित करता है कि प्लेसमेंट वैध है या नहीं।)

1. क्या इस कोड में बैकट्रैकिंग सही तरीके से लागू की गई है, और यदि नहीं, तो यह कैसे तय किया जाएगा?
2. मैं सॉल्वर को ठंड से कैसे रोक सकता हूं? यह लगभग 3 पंक्तियों को हल करता है और फिर फ्रीज करता है, अधिकांश मूल्यों को 9 एस में बदलता है।

कुछ कोड:

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

मुसीबत आ रही हैं कि आपके पुनरावर्ती कॉल में से कुछ, ठीक से परिणाम लौट रहे हैं नहीं है, तो अपने समाधान, जब यह पाया जाता है कुछ के बारे में भूल जाता है रिकर्सिव स्टैक का स्तर। यहाँ पहले ठीक है कि आप की जरूरत है, पुनरावर्ती mover में किए गए कॉल के लिए return जोड़ने है:

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 

आप भी अपनी solve_helper समारोह के विशेष मामले जहां पूर्व हल कोशिकाओं छोड़ में कुछ इसी तरह की जरूरत है। समारोह के अंत में होना चाहिए:

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

संपादित करें:

ठीक है, मैं कोड में कुछ और मुद्दों मिल गया है। उनमें से दो सॉल्वर के साथ तर्कसंगत मुद्दे हैं, और एक एक प्रदर्शन मुद्दा है जो हल करने के दौरान अजीब लगने के अलावा किसी भी वास्तविक समस्या का कारण नहीं बनता है।

मुद्दों:

1. सबसे पहले, आप नवीनतम कोड solve_helper ही बुला गया है, बल्कि mover बुला से कर रहे हैं। यह आगे बढ़ने से पहले एक अतिरिक्त फ़ंक्शन कॉल करता है (हालांकि मुझे लगता है कि यह वास्तव में सॉल्वर को तोड़ नहीं सकता है)।
2. दूसरा, अगर solve_helper 9 के लिए एक सेल करता है, पर फिर पीछे हट में (के बाद कुछ बाद में कोशिकाओं हल नहीं किया जा सकता है), 9 शून्य करने के लिए आगे उलटे पांव लौटने से पहले रीसेट नहीं होती है।
3. और आखिरकार, प्रदर्शन समस्या। 0 से कोशिकाओं को सेट करना उनके पुराने मान को प्रदर्शित होने से नहीं रोकता है। इसने # 2 में इस मुद्दे की तरह बहुत कुछ देखा, (बैकट्रैकिंग के बाद 9 एस पीछे छोड़ दिया गया) लेकिन वास्तव में यह केवल कॉस्मेटिक है।

पहले इस मुद्दे को ठीक करने के लिए आसान है। बस solve_helper को इसके बजाय mover कॉल पर कॉल करें। यह वास्तव में आपके द्वारा प्रश्न में डाले गए मूल कोड में था। solve_helper पर कॉल करने से वास्तव में गलत परिणाम नहीं मिलता है (क्योंकि solve_helper दूसरी बार पहले से भर चुके सेल को छोड़ देगा), लेकिन यह आपके रिकर्सन के प्रत्येक स्तर पर एक अनावश्यक अतिरिक्त फ़ंक्शन कॉल जोड़ता है।

दूसरे अंक में एक छोटे से अधिक जटिल है, और इस जहाँ आप कुछ बोर्डों पर अटक कर रहे हैं। आपको क्या करने की जरूरत है लाइन है कि else ब्लॉक यह वर्तमान में से बाहर self.set_cell(row, col, 0) करता है के लिए कदम है। वास्तव में, आप वास्तव में यह लूप के बाहर स्थानांतरित कर सकते हैं पूरी तरह से, अगर आप चाहते हैं (क्योंकि यह केवल वास्तव में जरूरी है कि आप कर रहे हैं वर्तमान सेल के लिए कोई भी मूल्य काम करने के बाद बैकट्रैकिंग)।

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 

अंत में, प्रदर्शन समस्या दूर करने की दो परिवर्तन की आवश्यकता है: यहाँ मैं क्या लगता है कि इस के पाश (भी return False बयान ऊपर जा रहा है) के लिए सबसे अच्छा व्यवस्था है। सबसे पहले, set_cell में सशर्त से छुटकारा पाएं। आप हमेशा प्रदर्शन को अपडेट करना चाहते हैं। अगला, update_textfield में, if ब्लॉक के बाहर कॉल करें ताकि यह हमेशा होता है (के तहत insert छोड़ें)। इससे ऐसा होता है कि शून्य पर सेल सेट करने से पिछले मान मिटा दिया जाएगा, लेकिन यह वास्तविक 0 वर्ण प्रदर्शित नहीं करेगा (यह कुछ भी नहीं दिखाएगा)।

मुझे लगता है कि यह करना चाहिए। ध्यान दें कि आप जिस एल्गोरिदम का उपयोग कर रहे हैं वह अभी भी बहुत धीमी है। a board I found on the internet in a quick Google search को हल करने में 122482 अनुमान और 5 मिनट से अधिक समय लगे, लेकिन अंततः यह काम किया। अन्य बोर्ड (विशेष रूप से जिनके लिए पहले कुछ खुली जगहों में 8s या 9s की आवश्यकता होती है) में और भी समय लग सकता है।