हनोई की मीनार

तीन खूँटियाँ, और डिस्कों का एक शंकु जिसमें सबसे बड़ी डिस्क सबसे नीचे है। पूरी मीनार को दाईं खूँटी पर ले जाएँ। एक बार में केवल एक डिस्क हिलाई जा सकती है, और बड़ी डिस्क कभी छोटी डिस्क पर नहीं रह सकती। सबसे छोटा हल 2ⁿ − 1 चालों का है: 1, 3, 7, 15, 31, और इसी तरह आगे। एक बार में एक डिस्क को किसी बड़ी डिस्क या खाली खूँटी पर रखें। पूरी मीनार को अंत में दाईं खूँटी पर पहुँचना है। सबसे छोटा हल 2ⁿ − 1 चालों का है। डिस्क खींचें, या एक खूँटी पर और फिर दूसरी पर क्लिक करें।

यह कैसे काम करता है

यह पेज खोलें। शुरुआती खूँटी पर चार डिस्कें रखी हैं। न्यूनतम पंद्रह चालें हैं।
सबसे ऊपर की डिस्क को दूसरी खूँटी पर खींचें, या एक खूँटी पर और फिर मनचाही खूँटी पर क्लिक करें। छोटी डिस्क पर बड़ी डिस्क स्वीकार नहीं होती।
सबसे छोटा हल देखने के लिए ‘हल करें’ दबाएँ, या ‘चरण’ से एक-एक कदम देखें। फिर PNG सहेजें।

एक डिस्क, और कभी बड़ी डिस्क छोटी पर नहीं

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

2ⁿ − 1 चालें, इससे कम नहीं

n डिस्कें ले जाने के लिए पहले सबसे बड़ी डिस्क के ऊपर की n − 1 डिस्कें रास्ते से हटाएँ, सबसे बड़ी डिस्क को एक बार हिलाएँ, फिर n − 1 डिस्कें उसके ऊपर ले जाएँ। अगर n − 1 डिस्कों में T चालें लगती हैं, तो n डिस्कों में 2T + 1 लगती हैं। यही 2ⁿ − 1 है: 1, 3, 7, 15, 31। यहाँ की सबसे ऊँची मीनार, आठ डिस्कें, 255 चालें लेती है।

वही पहेली, एक डिस्क कम

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