हनोई की मीनार के बारे में | नियम, 2ⁿ−1 और किंवदंती

तीन खूँटियाँ और डिस्कों का शंकु

बोर्ड पर तीन खूँटियाँ हैं। सभी डिस्कें अलग-अलग आकार की हैं और खूँटियों में पिरोई जाती हैं। शुरुआत में पूरा सेट एक खूँटी पर आकार के क्रम में रहता है, सबसे बड़ी नीचे और सबसे छोटी ऊपर, इसलिए ढेर एक शंकु जैसा होता है। लक्ष्य पूरी मीनार को दूसरी खूँटी पर ले जाना है।

तीन खूंटियों पर डिस्क वाली लकड़ी की हनोई की मीनार पहेली — लकड़ी की हनोई की मीनार पहेली। फोटो: PranavAmbhore, CC BY-SA 3.0

तीन नियम

1. एक बार में केवल एक डिस्क हिलाएँ। 2. एक चाल में किसी ढेर की सबसे ऊपर की डिस्क उठाकर दूसरे ढेर या खाली खूँटी पर रखी जाती है। 3. बड़ी डिस्क कभी छोटी डिस्क पर नहीं रह सकती। ये तीन नियम ही पूरा खेल हैं। इनके साथ हर वैध स्थिति डिस्कों को खूँटियों में बाँटने का एक तरीका है, जिसमें हर खूँटी क्रम में रहती है।

सबसे छोटा हल 2ⁿ − 1 है

n डिस्कों की मीनार को हल करने वाली सबसे कम चालें 2ⁿ − 1 हैं। एक डिस्क में 1 चाल लगती है। दो डिस्कों में 3। तीन में 7, चार में 15 और पाँच में 31। हर नई डिस्क पिछले हल को दोगुना करती है और सबसे बड़ी डिस्क को ले जाने वाली एक चाल जोड़ती है: अगर n − 1 डिस्कों में T चालें लगती हैं, तो n डिस्कों में 2T + 1 लगती हैं। यह पुनरावृत्ति ठीक 2ⁿ − 1 है। PictorX ऐप की सबसे ऊँची मीनार, आठ डिस्कें, 255 चालें लेती है। इससे छोटा कोई वैध रास्ता नहीं है।

पुनरावर्तन कैसे काम करता है

बची हुई खूँटी को सहायक खूँटी बनाकर n डिस्कों को शुरुआती खूँटी से लक्ष्य खूँटी पर ले जाने के लिए: 1. ऊपर की n − 1 डिस्कें शुरुआती खूँटी से सहायक खूँटी पर ले जाएँ। 2. सबसे बड़ी डिस्क को शुरुआती खूँटी से सीधे लक्ष्य खूँटी पर ले जाएँ। 3. n − 1 डिस्कें सहायक खूँटी से लक्ष्य खूँटी पर, सबसे बड़ी डिस्क के ऊपर ले जाएँ। चरण 2 वैध है क्योंकि सबसे बड़ी डिस्क किसी भी खूँटी पर रह सकती है। चरण 1 और 3 वही पहेली हैं, एक डिस्क कम। पुनरावर्तन एक अकेली डिस्क पर रुकता है, जो एक बार हिलती है। इसे खोलने पर 2ⁿ − 1 चालें मिलती हैं, और कोई भी चरण कभी बड़ी डिस्क को छोटी पर नहीं रखता।

डोमेन दे शॉन्तloup पर विशाल आउटडोर हनोई की मीनार — डोमेन दे शॉन्तloup पर विशाल हनोई की मीनार। फोटो: Als33120, CC BY-SA 4.0

64 सुनहरी डिस्कों की किंवदंती

फ़्रांसीसी गणितज्ञ Édouard Lucas ने यह पहेली 1883 में पेश की। इसके साथ उन्होंने काशी विश्वनाथ के एक भारतीय मंदिर की किंवदंती सुनाई, जहाँ पुजारी इन्हीं नियमों से 64 सुनहरी डिस्कों का ढेर हटाते हैं। किंवदंती कहती है कि जब आख़िरी चाल चली जाएगी, तब दुनिया ख़त्म हो जाएगी। चौंसठ डिस्कों में 2⁶⁴ − 1 चालें लगती हैं: 18,446,744,073,709,551,615। दिन-रात हर सेकंड एक सही चाल चलें, तब भी लगभग 585 अरब साल लगेंगे। पुजारी इसे पूरा नहीं कर पाएँगे।

गणितज्ञ एडुआर्द ल्यूका का चित्र — एडुआर्द ल्यूका (1842-1891), जिन्होंने 1883 में यह पहेली पेश की। सार्वजनिक डोमेन

PictorX में खेलें

हनोई की मीनार खोलें, शुरुआती खूँटी पर चार डिस्कों की मीनार पहले से रखी है। न्यूनतम पंद्रह चालें हैं। सबसे ऊपर की डिस्क को दूसरी खूँटी पर खींचें, या एक खूँटी पर और फिर मनचाही खूँटी पर क्लिक करें। कुंजियाँ 1, 2 और 3 भी यही करती हैं। छोटी डिस्क पर बड़ी डिस्क स्वीकार नहीं होती। ‘डिस्क’ 1 से 8 तक है, इसलिए आप 1, 3, 7, 15, 31, 63, 127 और 255 को सूत्र से मिला सकते हैं। ‘चरण’ सबसे छोटे हल की एक चाल चलाता है। ‘हल करें’ बाकी चलाता है। ‘3 डिस्क देखें’ पुनरावर्ती रणनीति को चलते हुए दिखाता है। ‘पूर्ववत करें’ और ‘फिर से करें’ आपकी चालों में आगे-पीछे जाते हैं। PNG सहेजें, या बोर्ड को PictorX संपादक में खोलें।

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

हनोई की मीनार के नियम क्या हैं?

एक बार में एक डिस्क हिलाएँ। किसी खूँटी की सबसे ऊपर की डिस्क उठाकर दूसरी खूँटी पर रखें। बड़ी डिस्क कभी छोटी डिस्क पर न रखें। पूरी मीनार एक खूँटी से शुरू होती है और उसे दूसरी पर ख़त्म होना होता है।

सबसे छोटे हल में कितनी चालें लगती हैं?

2ⁿ − 1। एक डिस्क में 1 चाल, दो में 3, तीन में 7, चार में 15 और पाँच में 31। हर नई डिस्क पिछले हल को दोगुना करती है और एक चाल जोड़ती है।

हनोई की मीनार का आविष्कार किसने किया?

फ़्रांसीसी गणितज्ञ Édouard Lucas ने इसे 1883 में पेश किया। काशी विश्वनाथ के पुजारियों और 64 सुनहरी डिस्कों की कहानी वह किंवदंती है जो उन्होंने पहेली के साथ जोड़ी।

64 डिस्कों में कितना समय लगेगा?

2⁶⁴ − 1 चालें, यानी 18,446,744,073,709,551,615। एक सेकंड में एक चाल के हिसाब से लगभग 585 अरब साल लगेंगे।