मेरे पास हाथ में एक समस्या है जो एन-क्वीन-प्रॉब्लम का एक रूपांतर है। समस्या यह है कि: 8 * 8 शतरंज की बिसात पर 4 रानियों और 1 नाइट को रखने का एक तरीका खोजें, ताकि इन टुकड़ों द्वारा सभी ब्लॉकों पर हमला किया जा सके। टुकड़ों के लिए एक-दूसरे पर हमला करना ठीक है।

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


आप लोगों का शुक्रिया। @ vish4071 @Karoly Horvath @M Oehm मैं जानवर बल का उपयोग करने पर विचार करूंगा और देखूंगा कि मुझे क्या मिला।

2
antande 16 नवम्बर 2015, 09:35

2 जवाब

सबसे बढ़िया उत्तर

Brute Force का उपयोग करें। इसका जवाब आपको कम समय में देना चाहिए।

आपके पास विचार करने के लिए 64 वर्ग हैं और 5 टुकड़े करने के लिए। बस 5 वर्गों का चयन करें और 5 टुकड़े डालें और देखें कि क्या यह परिदृश्य सभी वर्गों को कवर करता है। यह C(64,5) * 5 तरीकों से किया जा सकता है, जो ~3.8e7 है, जो अब एक मानक मशीन पर 1s के तहत आसानी से गणना करने योग्य है।

इसके अलावा, आप कुछ संगणना को कम कर सकते हैं यदि आप 4 रानियों को चुनिंदा 4 में से 4 को 64 वर्ग में रखते हैं और फिर शेष वर्गों को कवर करने के लिए नाइट को जगह देते हैं। यह लगभग C(64,4) * k अभिकलन ले जाएगा, जो ~1e6 है।

3
vish4071 16 नवम्बर 2015, 07:43

मुझे नहीं लगता कि एक भोली एल्गोरिथ्म को किसी भी तरह के अनुकूलन की आवश्यकता है क्योंकि यह शायद वैसे भी तेज़ हो ... लेकिन, यहाँ यह है:

आप हमेशा पहली चाल को किसी एक क्वार्टर (जैसे: ऊपरी बाएँ) तक सीमित कर सकते हैं, क्योंकि बाकी समाधानों को मिरर करके या घुमाकर उत्पन्न किया जा सकता है।

आप कवर किए गए स्थानों की गणना कर सकते हैं, और एक सीमा है कि एक टुकड़ा कितना कवर कर सकता है (एक रानी के लिए 22 और एक राजा के लिए 9), इसलिए आप इसे एक निराशाजनक शाखा को जल्दी समाप्त करने के लिए एक नियम के रूप में उपयोग कर सकते हैं।

नोट: चूँकि आपके पास केवल 4 रानियाँ हैं, 2 को एक ही पंक्ति या कॉलम में रखना शायद एक बुरा विचार है। आप कोशिश कर सकते हैं कि प्रतिबंध के रूप में।

0
Karoly Horvath 16 नवम्बर 2015, 07:24