एरलांग में बैकट्रैकिंग

Question

सबसे पहले मेरी अंग्रेजी के लिए खेद है।

मैं एरलांग में बैकट्रैकिंग एल्गोरिदम का उपयोग करना चाहता हूं। यह आंशिक रूप से भरे सुडोकस को हल करने के अनुमान के रूप में कार्य करेगा। एक 9 x 9 सुडोकू 81 तत्वों की सूची के रूप में संग्रहीत किया जाता है, जहां प्रत्येक तत्व उस संभावित संख्या को संग्रहीत करता है जो उस सेल में जा सकता है।

एक 4x4 सुडोकू के लिए मेरा प्रारंभिक समाधान इस तरह दिखता है: [[1], [3], [2], [4], [4], [2], [3], [1], [ 2,3], [4], [1], [2,3], [2,3], [1], [4], [2,3]]

इस सुडोकू में 2 समाधान हैं। मुझे दोनों को लिखना है। उस प्रारंभिक समाधान के बाद, मुझे बैकट्रैकिंग एल्गोरिदम लागू करने की आवश्यकता है, लेकिन मुझे नहीं पता कि इसे कैसे बनाया जाए।

मेरा विचार निश्चित तत्वों को फिक्स्डलिस्ट नामक एक नई सूची में लिखना है जो एकाधिक समाधान कोशिकाओं को [] में बदल देगा।

उपर्युक्त उदाहरण के लिए फिक्स्डलिस्ट इस तरह दिखता है: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [], [1], [4], []]

यहां से मेरे पास "नमूना" है, मैं समाधान सूची में सबसे कम लंबाई की तलाश करता हूं, 1 के बराबर नहीं है, और मैं इस सेल की पहली संभावित संख्या आज़माता हूं और मैंने इसे उस निश्चित सूची में डाल दिया है। यहां मेरे पास कोशिकाओं को अद्यतन करने के लिए एक एल्गोरिदम है और जांच करता है कि यह अभी भी एक हल करने योग्य सुडोकू है या नहीं। यदि नहीं, तो मुझे नहीं पता कि कैसे एक को पीछे हटाना है और एक नया प्रयास करना है। मुझे इसका छद्म कोड पता है और मैं इसे अनिवार्य भाषाओं के लिए उपयोग कर सकता हूं लेकिन एरलांग के लिए नहीं। (प्रोलॉग वास्तव में बैकट्रैक एल्गोरिदम लागू किया गया था, लेकिन erlang नहीं था)

कोई विचार?

Answer 1

पुन: मेरे bactracking कार्य करता है।

ये सामान्य कार्य हैं जो प्रोलॉग इंजन के समान बैक-ट्रैकिंग और लॉजिकल वैरिएबल को संभालने के लिए एक ढांचा प्रदान करते हैं। आपको फ़ंक्शन (भविष्यवाणी) प्रदान करना होगा जो प्रोग्राम तर्क का वर्णन करता है। यदि आप उन्हें लिखते हैं तो आप प्रोलॉग में करेंगे, मैं आपको दिखा सकता हूं कि उन्हें एरलांग में कैसे अनुवादित किया जाए। जैसे

p(Next0) -> 
    Next1 = fun() -> s(Next0) end, 
    Next2 = fun() -> r(Next1) end, 
    q(Next2). 

यहाँ मैं निरंतरता को छोड़कर सभी अन्य तर्कों की अनदेखी कर रहा हूँ कुछ में prolog में

p :- q, r, s. 

: बहुत संक्षेप में आप की तरह कुछ अनुवाद करते हैं।

मुझे आशा है कि इससे कुछ मदद मिलती है। जैसा कि मैंने कहा था कि यदि आप अपने एल्गोरिदम का वर्णन करते हैं तो मैं उन्हें अनुवाद करने में आपकी सहायता कर सकता हूं, मैं एक अच्छा उदाहरण ढूंढ रहा हूं। आप निश्चित रूप से अपने आप से ऐसा कर सकते हैं लेकिन यह कुछ मदद प्रदान करता है।

Answer 2

बाहर चेक रॉबर्ट Virding के ब्लॉग में इन लेखों:

http://rvirding.blogspot.com/2009/03/backtracking-in-erlang-part-1-control.html http://rvirding.blogspot.com/2009/04/backtracking-in-erlang-part-2-passing.html