मैं कंप्यूटर प्रोग्राम के साथ लॉग ढेर लकड़ी की पहेली को कैसे हल कर सकता हूं?

Question

क्या कोई सुझाव दे सकता है कि कंप्यूटर प्रोग्राम का उपयोग कर लॉग पाइल लकड़ी की पहेली को कैसे हल किया जाए?

यहाँ देखें पहेली कल्पना करने के लिए: http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm

चित्र केवल टुकड़े में से कुछ पता चलता है। 10 टुकड़ों का पूरा सेट 1 के रूप में कॉन्फ़िगर किया गया है, जिसमें 1 पेग का प्रतिनिधित्व होता है, -1 एक छेद का प्रतिनिधित्व करता है और 0 न तो एक पेग और न ही छेद का प्रतिनिधित्व करता है।
-1,1,0, -1,0
1,0,1,0,0
1, -1,1,0,0
-1, -1,0,0, -1
-1,1,0,1,0
0,1,0,0,1
1,0, -1,0, -1
0, -1,0,1,0
0,0, -1,1, -1
1,0, -1,0,0

टुकड़े को 5 परतों की दो परतों में इंटरलाक्ड किया जा सकता है, शीर्ष परत के साथ 90 डिग्री पर शीर्ष परत जैसा उपर्युक्त लिंक में दिखाया गया है।

मैंने पहले ही जावा का उपयोग करके इस समस्या का हल किया है, लेकिन मुझे लगता है कि यह एक बेवकूफ समाधान था और मुझे कुछ और परिष्कृत समाधान देखने में दिलचस्पी है। या तो एक सामान्य दृष्टिकोण का सुझाव दें या अपनी पसंद की भाषा में एक कार्य कार्यक्रम प्रदान करने के लिए स्वतंत्र महसूस करें।

मेरा दृष्टिकोण "लॉग" की सरणी बनाने के लिए उपरोक्त संख्यात्मक नोटेशन का उपयोग करना था। तब मैंने एक संयोजन/क्रमपरिवर्तन जनरेटर का उपयोग लॉग की सभी संभावित व्यवस्थाओं को करने के लिए किया जब तक कोई समाधान नहीं मिला, जहां सभी चौराहे शून्य से बराबर होती हैं (यानी पेग टू होल, होल टू पेग या रिक्त स्थान पर खाली)। मैंने दिए गए क्रमपरिवर्तन के लिए पहले विफल चौराहे का पता लगाने और अगले क्रमपरिवर्तन पर जाने के लिए कुछ गति-अप का उपयोग किया।

मुझे आशा है कि आपको यह उतना दिलचस्प लगेगा जितना मेरे पास है।

धन्यवाद, क्रेग।

Answer 1

जे Elston से सलाह के बाद, मैं इसे निम्नलिखित स्यूडोकोड का उपयोग कर लागू करना होगा:

Read in the pieces 
Annotate each piece with its number of pegs and holes 
Generate all possible base layers (10 over 5 = 252, selecting 5 from the set), 
    so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes) 
    For each base layer, (5! = 120 of them, permuting the 'below' pieces) 
     compute 'rotated pieces' for the base layer 
     if one-to-one match between top layer and rotated base-layer pieces, 
      report successful solution 

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

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

Answer 2

प्रोलॉग इस प्रकार की समस्याओं के लिए लोकप्रिय है। मैंने कुछ simpler puzzle problems स्थापित किए हैं जिनके पास प्रोलॉग में अपेक्षाकृत अच्छे समाधान हैं।

कार्यों और बैकट्रैकिंग का उपयोग करके, हास्केल में इन प्रकार की समस्याओं को हल करने के बहुत ही शानदार तरीके हैं। मेरे एक दोस्त ने एक बहुत ही परेशान भौतिक पहेली हल की — Puzzling Pets — हस्केल के 200 से अधिक लाइनों में, सभी टुकड़ों और सब कुछ के विवरण सहित।   प्रासंगिक तकनीकों को सीखने का अच्छा तरीका जॉन ह्यूजेस के पेपर Why Functional Programming Matters को पढ़ना होगा, Haskell Platform इंस्टॉल करें, और अपना हाथ आजमाएं।

Answer 3

यह समस्या Boolean satisfiability problem का एक रूप प्रतीत होता है। यदि ऐसा है, तो सबसे अच्छा ज्ञात दृष्टिकोण ब्रूट फोर्स है।

लेकिन कुछ समरूपताएं हैं, और समस्या के कुछ गुण जो आपको कोशिश करने के लिए आवश्यक समाधानों की संख्या को कम करने दे सकते हैं।उदाहरण के लिए -

• आप में लॉग विभाजित करते दो 5-टुकड़ा टॉप जरूरतों में ऊपर और नीचे, # टॉप में खूंटे # तल में छेद से मेल खाना चाहिए, और # छेद सबसेट बोटॉम में # pegs से मिलान करने के लिए, और बोटॉम में # फ्लैटों से मेल खाने के लिए शीर्ष में # फ्लैटों को की आवश्यकता है। यदि # pegs और # छेद मिलते हैं, तो # फ्लैट्स भी मेल खाते हैं, इसलिए आपको को # फ्लैटों की जांच करने की आवश्यकता नहीं है।
• 10 * 9 * 8 * 7 * 6 तरीके हैं जिन्हें आप लॉग को दो 5-टुकड़े सबसेट में विभाजित कर सकते हैं। (एक बार जब आप है उठाया के लिए सबसेट टॉप पहले 5 लॉग, शेष लॉग सबसेट नीचे में हैं।
• जब आप किसी 5-टुकड़ा सबसेट का परीक्षण, वहाँ 5 * 8 * 6 * 4 * 2 तरीके हैं आप कर सकते हैं लॉग की एक परत व्यवस्थित करें। यही है, जब आप लॉग 1 चुनते हैं, तो 4 शेष लॉग होते हैं। दूसरे लॉग के लिए, आप चार से चुन सकते हैं, और दो तरीकों से इसे पहले लॉग के संबंध में के साथ उन्मुख किया जा सकता है
• एक बार आपके पास आधार परत हो जाने के बाद, आप एक बार में दूसरी परत से प्रत्येक लॉग को फिट करने का प्रयास कर सकते हैं, जब तक कि आप फिट न हों। उस बिंदु पर, आप वर्तमान आधार परत लॉग व्यवस्था को छोड़ देते हैं और अगले एक को आजमाएं।

Answer 4

मेरे पास जावास्क्रिप्ट में एक (गन्दा!) समाधान है, लेकिन इसे पोस्ट करने में कठिनाई हुई है। उपयोग किया जाने वाला मूल एल्गोरिदम है: कुल 10 लॉग से 5 लॉग के सभी पुनरावृत्तियों को ढूंढें, और 5 लॉग के प्रत्येक सेट के साथ लॉग को उलटने के साथ हर पुनरावृत्ति संभव हो। इन राज्यों में से प्रत्येक के लिए, हम जानेंगे कि लॉग के किस पैटर्न को शीर्ष पर रखा जाना चाहिए। इसलिए, हम तब निर्धारित करते हैं कि शेष 5 लॉग शीर्ष पर रखा जा सकता है या नहीं।

कौन सा एक समाधान के इस प्रतिनिधित्व की ओर जाता है:

(Bottom, right-> left) 
[0,0,1,-1,1],[-1,-1,0,0,-1],[0,0,1,0,1],[-1,1,0,-1,0],[1,0,-1,0,0] 
(Top, up->down) 
[0,1,0,1,-1],[0,1,0,-1,0],[-1,0,-1,0,1],[1,0,0,1,0],[-1,1,-1,0,0] 


0 - flat 
1 - dowel 
-1 - hole