एन-क्वींस एक दिलचस्प कोडिंग चुनौती है जहां आपको एन क्वीन्स को N * N बोर्ड पर रखना होता है। ।
यह इस तरह दिखता है:
एक रानी सभी दिशाओं में घूम सकती है:
- ऊर्ध्वाधर
- क्षैतिज
- विकर्ण
समाधान (कई हो सकते हैं) सभी रानियों को बोर्ड पर रखना चाहिए और हर रानी को हर दूसरी रानी की पहुंच से बाहर होना चाहिए।
इस लेख में आप जानेंगे कि मैंने इसका समाधान कैसे निकाला।
योजना
इस तरह की चुनौतियों का समाधान करते समय एक योजना को सादे अंग्रेजी में लिखना शुरू करने के लिए एक अच्छी जगह है।
इससे आपको यह स्पष्ट करने में मदद मिलती है कि समस्या क्या है और इसे हल करने के उपाय क्या हैं।
अगर आपको अपनी योजना लिखने में समस्या हो रही है सुनिश्चित करें कि आप समस्या को 100% समझते हैं ।
एन-क्वींस समाधान के लिए मेरी योजना:
- शुरू @ स्थिति 0,0
- यदि वैध स्थिति है:रानी रखें, अग्रिम कॉलम (+ 1), पंक्ति को 0 पर सेट करें
- ऊपर, नीचे, बाएँ, दाएँ, विकर्ण की जाँच करें
- अन्य:1 वर्ग आगे बढ़ें
- ऊपर जाएं (पंक्ति + 1) जब तक वर्तमान स्थिति ==n
- बैकट्रैक जब रानी को वर्तमान कॉलम में नहीं रखा जा सकता
- पिछली रानी को हटाएं
- पंक्ति + 1 के साथ पंक्ति और स्तंभ को अंतिम रानियों की स्थिति पर सेट करें
मैंने शुरू में जो लिखा था, यह उसका एक साफ-सुथरा संस्करण है।
मैं उन चरणों के बारे में गहराई से जानकारी लेता हूं, जिन्हें लागू करने से पहले मुझे अधिक विवरण की आवश्यकता होती है।
अब :
आपकी योजना सही नहीं होगी (मेरा नहीं था) लेकिन यह आपको एक विचार देगी कि किस दिशा में काम करना है।
यदि आप एक ठोस योजना नहीं लिख सकते हैं समाधान तलाशने में कुछ भी गलत नहीं है …
…समझें कि समाधान कैसे काम करता है, फिर अपना खुद का लिखें।
मान्य मूव्स ढूँढना
यह जांचने के लिए कि क्या कोई पद वैध है, हमें कई दिशाओं में देखना होगा।
2D बोर्ड के साथ खिलवाड़ करने के बजाय, मैंने रानियों की एक सरणी रखने का फैसला किया बोर्ड में अपने पदों के साथ।
फिर हम रानियों की इस सरणी को उस स्थिति के विरुद्ध जाँचते हैं जिसे हम मान्य करना चाहते हैं।
उदाहरण के लिए, पंक्ति जाँच के लिए:
def queen_in_row(row) @queens_in_board.find {|r, c| r ==पंक्ति }अंत यदि पंक्ति ली जाती है या नहीं तो यह एक रानी लौटाएगा।
आपको यह जांचने की ज़रूरत नहीं है कि कॉलम मुफ़्त है या नहीं क्योंकि हम रानी रखने के बाद अगले कॉलम पर जाते हैं ।
विकर्णों के लिए कुछ अतिरिक्त काम करना पड़ता है क्योंकि उनमें से 4 हैं।
यहाँ दाहिने ऊपरी विकर्ण के लिए कोड है:
def right_upper_diagonal_for(row, column, n) विकर्ण =[] पंक्ति तक ==n || कॉलम ==एन विकर्ण <<[पंक्ति + =1, कॉलम + =1] अंत विकर्ण भेजें
अन्य विकर्ण समान हैं, केवल अंतर लूप और दिशा (पंक्ति + 1 / पंक्ति -1) की स्थितियों में है।
इसे ठीक करने में थोड़ा परीक्षण और त्रुटि हुई, लेकिन यह ठीक है।
इन विधियों का अलग-अलग परीक्षण करना महत्वपूर्ण है ताकि यह सुनिश्चित हो सके कि वे काम करती हैं . जब आपके पास काम करने के तरीकों का एक सेट होता है, तो आप अपना पूरा समाधान बनाने के लिए उन्हें एक साथ रख सकते हैं।
यहाँ वह तरीका है जो बोर्ड में प्रत्येक रानी के खिलाफ सभी विकर्णों और जाँचों को एक साथ खींचता है:
def रानी_in_diagonal (पंक्ति, स्तंभ, n) विकर्ण =right_upper_diagonal_for (पंक्ति, स्तंभ, n) + left_upper_diagonal_for (पंक्ति, स्तंभ, n) + left_lower_diagonal_for (पंक्ति, स्तंभ, n) + right_lower_diagonal_for (पंक्ति, स्तंभ, n) विकर्ण ।कोई? {|आर, सी| r ==पंक्ति &&c ==कॉलम } || विकर्ण।कोई? {|आर, सी| @queens_in_board.any? {|क्यूआर, क्यूसी| r ==qr &&c ==qc } }अंत बैकट्रैकिंग कैसे लागू करें
इन गैर-तुच्छ चुनौतियों को हल करने के लिए आपको एक महत्वपूर्ण अंतर्दृष्टि, तकनीक या एल्गोरिदम जानने की आवश्यकता है।
एन-क्वींस के मामले में तकनीक पीछे हट रही है ।
बैकट्रैकिंग कुछ पिछली कार्रवाई को पूर्ववत कर रहा है (जैसे बोर्ड पर एक रानी को रखना) और एक अलग कॉन्फ़िगरेशन के साथ फिर से प्रयास करना।
मुझे लगा कि यह सबसे कठिन हिस्सा होगा, लेकिन यह बहुत आसान निकला।
यह पता लगाने के लिए मैंने थोड़ा अनुकरण किया।
मैंने अपने लिए एक बोर्ड बनाया और कुछ रानियों को दर्शाने वाले बक्से :
फिर मैंने एल्गोरिदम को अनुकरण करने के लिए बस बोर्ड के चारों ओर बक्से (सीधे अपने माउस के साथ) ले जाया।
यह रहा कोड:
जबकि पंक्ति>=n पंक्ति =@queens_in_board[-1][0] + 1 कॉलम =@queens_in_board[-1][1] "बैकट्रैकिंग, हटा दिया गया:#{@queens_in_board.pop}"end आप इसे अन्य समस्याओं के लिए भी कर सकते हैं जब आप फंस जाते हैं, इसे किसी ड्राइंग प्रोग्राम पर या कागज पर भी ड्रा करें और इसके साथ खेलें।
यह कैसे काम करता है इसका सार है:
- हम ऊपर जाते रहते हैं, अगर हम बोर्ड के शीर्ष पर पहुंच जाते हैं तो इसका मतलब है कि हम इस कॉलम पर एक रानी को फिट नहीं कर सकते हैं
- हम वर्तमान स्थिति को अंतिम रानी पर सेट करके और उसे बोर्ड से हटाकर पीछे हट जाते हैं
- अगर हम इस स्थिति से रानी को नहीं रख सकते हैं तो हम फिर से पीछे हट जाते हैं
पंक्ति स्थिति पर +1 यह है कि कैसे हम अंतिम रानी को उसकी स्थिति बदलने के लिए आगे बढ़ाते हैं &नए बोर्ड कॉन्फ़िगरेशन खोलें।
इस कोड को n =4 के लिए चलाते समय (n =2 और n =3 के लिए कोई समाधान नहीं हैं):
"0 0 पर रखना""2 1 पर रखना"बैकट्रैकिंग, हटाया गया:[2, 1]"3 1 पर रखना""1 2 पर रखना"बैकट्रैकिंग, हटाया गया:[1, 2]बैकट्रैकिंग, हटाया गया:[ 3, 1]बैकट्रैकिंग, हटाया गया:[0, 0]"1 0 पर रखना""3 1 पर रखना""0 2 पर रखना""2 3 पर रखना"
यह gif एल्गोरिथम का एक दृश्य उदाहरण है:
पूर्ण कोड
def Solve_n_queens(n) @queens_in_board =[] row =0 column =0 जब तक @queens_in_board.size ==n अगर queen_in_row(row) || queen_in_diagonal(row, column, n) row +=1 जबकि row>=n row =@queens_in_board[-1][0] + 1 column =@queens_in_board[-1][1] कहते हैं "बैकट्रैकिंग, डिलीट किया गया:#{@ क्वीन्स_इन_बोर्ड.पॉप}" अंत में जगह_क्वीन (पंक्ति, कॉलम) पी "#{पंक्ति} #{कॉलम}" पर रखकर पंक्ति =0 कॉलम + =1 अंत अंत @queens_in_boardenddef रानी_इन_रो (पंक्ति) @queens_in_board.find { |r, c | r ==पंक्ति }enddef रानी_इन_विकर्ण (पंक्ति, स्तंभ, n) विकर्ण =right_upper_diagonal_for (पंक्ति, स्तंभ, n) + left_upper_diagonal_for (पंक्ति, स्तंभ, n) + left_lower_diagonal_for (पंक्ति, स्तंभ, n) + right_lower_diagonal_for(पंक्ति, स्तंभ, n) ) विकर्ण। कोई? {|आर, सी| r ==पंक्ति &&c ==कॉलम } || विकर्ण।कोई? {|आर, सी| @queens_in_board.any? {|क्यूआर, क्यूसी| r ==qr &&c ==qc } }enddef top_row?(row, n) row ==nenddef place_queen(row, column) @queens_in_board <<[row, column] enddef right_upper_diagonal_for (पंक्ति, कॉलम, n) विकर्ण =[ ] पंक्ति तक ==n || स्तंभ ==n विकर्ण <<[पंक्ति + =1, स्तंभ + =1] अंत विकर्णsenddef left_upper_diagonal_for (पंक्ति, स्तंभ, n) विकर्ण =[] पंक्ति तक ==n || कॉलम ==0 विकर्ण <<[पंक्ति + =1, कॉलम - =1] अंत विकर्णसेंडडेफ right_lower_diagonal_for (पंक्ति, स्तंभ, एन) विकर्ण =[] पंक्ति तक ==0 || कॉलम ==एन विकर्ण <<[पंक्ति - =1, कॉलम + =1] अंत विकर्णसेंडडेफ लेफ्ट_लोवर_डायगोनल_फॉर (पंक्ति, कॉलम, एन) विकर्ण =[] जब तक पंक्ति ==0 || कॉलम ==0 विकर्ण <<[पंक्ति - =1, कॉलम - =1] अंत विकर्ण सेंडडेफ प्रिंट_बोर्ड (एन) बोर्ड =ऐरे। नया (एन) {ऐरे। नया (एन) { "।" } } @queens_in_board.each { |queen| बोर्ड [क्वीन [0]] [क्वीन [1]] ="क्यू" } बोर्ड.मैप {|एन| n.join("|") }.reverseendpsolve_n_queens(4)p Solve_n_queens(5)प्रिंट_बोर्ड(5) डालता है पुनरावर्ती संस्करण
यह एक वैकल्पिक संस्करण है जो सभी संभावित समाधान ढूंढता है।
defsolve_n_queens(n, column =0, queens_in_board =[]) @queens_in_board =queens_in_board n.times do |row| जब तक क्वीन_इन_रो (पंक्ति) || Queen_in_diagonal(row, column, n) place_queen(row, column)solve_n_queens(n, column + 1, @queens_in_board) remove_last_queen एंड एंड पुट प्रिंट_बोर्ड(n) अगर @queens_in_board.size ==nend
केवल एक चीज जो बदलती है वह है solve_n_queens विधि।
यह संस्करण सभी आंशिक समाधानों का पता लगाने के लिए रिकर्सन (एक विधि जो स्वयं को कॉल करता है) का उपयोग करता है।
जब एक पूर्ण समाधान मिल जाता है तो हम इसे print_board . का उपयोग करके प्रिंट करते हैं विधि।
सारांश
आपने रूबी में एन-क्वींस कोडिंग चुनौती और इसे कैसे हल किया जाए, इसके बारे में सीखा। आपने यह भी सीखा है कि अपनी समस्या को सुलझाने के कौशल को कैसे सुधारें।
अगर आपको यह लेख पसंद आया हो तो कृपया इसे किसी ऐसे व्यक्ति के साथ साझा करें जो इससे लाभान्वित हो सके।
पढ़ने के लिए धन्यवाद!