घोड़े के भ्रमण के बारे में | वार्न्सडॉर्फ़ का नियम, खुले और बंद भ्रमण

एक पुरानी पहेली

9वीं सदी में भारतीय कवि रुद्रट द्वारा लिखे काव्यालंकार में एक पद आधी बिसात पर इस तरह रखा गया है कि उसे घोड़े के रास्ते के साथ-साथ पढ़ा जा सके। लियोनहार्ड यूलर ने 1759 में घोड़े के भ्रमण का पहला गणितीय अध्ययन लिखा, जिसमें भ्रमण बनाने और उन्हें बंद भ्रमणों में बदलने के तरीके थे।

ग्राफ़ में एक पथ

हर खाने को एक बिंदु और घोड़े की हर चाल को दो बिंदुओं के बीच एक रेखा मानें। तब घोड़े का भ्रमण एक ऐसा पथ है जो हर बिंदु पर ठीक एक बार जाता है, जिसे गणितज्ञ हैमिल्टोनियन पथ कहते हैं; बंद भ्रमण एक हैमिल्टोनियन चक्र है। ज़्यादातर नेटवर्कों में ऐसा पथ ढूँढना बहुत कठिन होता है। घोड़े का नेटवर्क उदार है: उसमें इतने भ्रमण हैं कि एक अच्छा नियम जल्दी ही एक ढूँढ लेता है।

वार्न्सडॉर्फ़ का नियम

एच. सी. वॉन वार्न्सडॉर्फ़ ने 1823 में अपना नियम बताया: हमेशा उस खाने पर कूदें जिससे आगे सबसे कम चालें बचती हैं। किनारे के खानों के पड़ोसी कम होते हैं, इसलिए यह नियम उन्हें अकेला छोड़ देने के बजाय उन पर जल्दी जाता है। जब दो खाने बराबर हों, तो किसी एक को चुनना पड़ता है, और बदकिस्मत चुनाव से घोड़ा फिर भी अटक सकता है। ऐप में सुनहरी संख्याएँ उन खानों को दिखाती हैं जिन्हें यह नियम चुनेगा।

बैकट्रैकिंग से खोज

‘हल करें’ वार्न्सडॉर्फ़ के क्रम का पालन करता है, लेकिन उस पर आँख मूँदकर भरोसा नहीं करता। यह पहले गहराई में खोजता है, और जैसे ही कोई ऐसा खाना, जिस पर घोड़ा अभी नहीं गया, पहुँच से बाहर हो जाता है, वह उस शाखा को छोड़कर अगली चाल आज़माता है। 10×10 तक के बोर्डों पर यह आमतौर पर तुरंत भ्रमण ढूँढ लेता है। जब आपके अपने रास्ते ने घोड़े को घेर लिया हो, तो यह पहले कुछ चालें पीछे जाता है।

रंग और बंद भ्रमण

घोड़े की हर चाल खाने का रंग बदल देती है। 5×5 जैसे विषम बोर्ड पर कोने वाले रंग के खाने दूसरे रंग से एक ज़्यादा होते हैं, इसलिए भ्रमण को कोने वाले रंग पर ही शुरू और ख़त्म होना चाहिए। वहाँ बंद भ्रमण असंभव है, क्योंकि बारी-बारी से रंग बदलने वाले चक्कर में दोनों रंगों के खाने बराबर होते हैं। सम बोर्डों पर बंद भ्रमण 6×6 और उससे बड़े आकार पर होते हैं।

PictorX में आज़माएँ

घोड़े का भ्रमण खोलें और शुरू करने के लिए किसी खाने पर क्लिक करें। हाइलाइट किए गए खाने वैध छलाँगें हैं, सुनहरी संख्या वार्न्सडॉर्फ़ की पसंद है, और बोर्ड आपकी चालों का क्रम याद रखता है। ‘आकार’ बोर्ड को 5×5 से 10×10 तक सेट करता है, ‘बंद भ्रमण’ चुनने पर ‘हल करें’ एक बंद चक्कर ढूँढता है, और ‘पूर्ववत करें’ कोई भी चाल वापस लेता है। पूरे हुए रास्ते को PNG के रूप में सहेजें।

अक्सर पूछे जाने वाले प्रश्न

घोड़े के भ्रमण का अध्ययन सबसे पहले किसने किया?

भ्रमण उनके गणितीय अध्ययन से बहुत पहले से ज्ञात थे। लियोनहार्ड यूलर ने 1759 में पहला गणितीय विवेचन लिखा, और वार्न्सडॉर्फ़ ने 1823 में अपना नियम दिया।

क्या हर बोर्ड पर भ्रमण होता है?

5×5 और उससे बड़े वर्गाकार बोर्डों पर खुले भ्रमण होते हैं, और 6×6 और उससे बड़े सम बोर्डों पर बंद भ्रमण भी होते हैं। 2×2, 3×3 और 4×4 के बोर्डों पर कोई भ्रमण होता ही नहीं।

शतरंज की बिसात पर कितने भ्रमण होते हैं?

अगर किसी भ्रमण और उसी भ्रमण को उल्टी दिशा में चलने को अलग-अलग गिना जाए, तो 26,534,728,821,064 बंद भ्रमण हैं। खुले भ्रमणों की संख्या लगभग 19.6 क्वाड्रिलियन है।

क्या PictorX कुछ अपलोड करता है?

नहीं। बोर्ड आपके ब्राउज़र के कैनवास पर बनता है। ‘सहेजें’ से PNG डाउनलोड होता है, और ‘संपादित करें’ से वह चित्र PictorX संपादक में खुलता है।