N-क्वीन्स एक दिलचस्प कोडिंग चुनौती है जहां आपको N * N बोर्ड पर N क्वीन्स रखनी होती हैं।
यह ऐसा दिखता है:
एक क्वीन्स सभी दिशाओं में चल सकती है:
- वर्टिकल
- हॉरिजॉन्टल
- डायगोनल
समाधान (कई हो सकते हैं) को बोर्ड पर सभी क्वीन्स रखनी चाहिए और हर क्वीन्स हर दूसरी क्वीन्स की पहुंच से बाहर होनी चाहिए।
इस लेख में आप सीखेंगे कि मैं समाधान तक कैसे पहुंचा।
योजना
इस तरह की चुनौतियों को हल करते समय एक अच्छी शुरुआत सादे अंग्रेजी में एक योजना लिखना है।
यह आपको समस्या क्या है और इसे हल करने के चरणों पर स्पष्ट होने में मदद करता है।
यदि आपको अपनी योजना लिखने में परेशानी हो रही है सुनिश्चित करें कि आप समस्या को 100% समझते हैं।
N-क्वीन्स समाधान के लिए मेरी योजना:
- पोजीशन 0,0 पर शुरू करें
- यदि वैध पोजीशन: क्वीन्स रखें, कॉलम आगे बढ़ाएं (+ 1), पंक्ति को 0 पर सेट करें
- ऊपर, नीचे, बाएं, दाएं, डायगोनल जांचें
- अन्यथा: 1 वर्ग आगे बढ़ें
- ऊपर जाएं (पंक्ति + 1) जब तक वर्तमान पोजीशन == n न हो
- बैकट्रैक जब क्वीन्स को वर्तमान कॉलम में नहीं रखा जा सकता
- अंतिम क्वीन्स को हटाएं
- पंक्ति और कॉलम को अंतिम क्वीन्स की पोजीशन पर सेट करें पंक्ति + 1 के साथ
यह मेरे द्वारा शुरू में लिखी गई योजना का एक क्लीनर संस्करण है।
मैं उन चरणों पर गहराई से जाता हूं जिन्हें लागू करने से पहले अधिक विवरण की आवश्यकता होती है।
अब:
आपकी योजना परफेक्ट नहीं होगी (मेरी भी नहीं थी) लेकिन यह आपको इस बात का अंदाजा देगी कि किस दिशा में काम करना है।
यदि आप एक ठोस योजना नहीं लिख सकते तो समाधान देखना गलत नहीं है...
...समझें कि समाधान कैसे काम करता है फिर अपना खुद का लिखें।
वैध चालें ढूंढना
यह जांचने के लिए कि कोई पोजीशन वैध है या नहीं, हमें कई दिशाओं में देखना होगा।
2D बोर्ड के साथ गड़बड़ करने के बजाय, मैंने बोर्ड में उनकी पोजीशन के साथ क्वीन्स की एक सरणी रखने का फैसला किया।
फिर हम इस क्वीन्स की सरणी को उस पोजीशन के खिलाफ जांचते हैं जिसे हम मान्य करना चाहते हैं।
उदाहरण के लिए, पंक्ति जांच के लिए:
def queen_in_row(row) @queens_in_board.find { |r, c| r == row } end
यह एक क्वीन्स लौटाएगा यदि पंक्ति ली गई है या यदि नहीं तो nil।
आपको यह जांचने की ज़रूरत नहीं है कि कॉलम फ्री है क्योंकि क्वीन्स रखने के बाद हम अगले कॉलम पर चले जाते हैं।
डायगोनल्स के लिए इसमें कुछ अतिरिक्त काम लगता है क्योंकि उनमें से 4 हैं।
दाएं ऊपरी डायगोनल के लिए यहां कोड है:
def right_upper_diagonal_for(row, column, n) diagonals = [] until row == n || column == n diagonals << [row += 1, column += 1] end diagonals end
अन्य डायगोनल्स समान हैं, केवल अंतर लूप की शर्तों और दिशा (पंक्ति + 1 / पंक्ति - 1) में है।
इसे सही करने में थोड़ा ट्रायल और एरर लगा, लेकिन यह ठीक है।
इन मेथड्स को आइसोलेशन में टेस्ट करना महत्वपूर्ण है ताकि यह सुनिश्चित हो सके कि वे काम करते हैं। जब आपके पास काम करने वाले मेथड्स का एक सेट होता है तो आप उन्हें अपने पूर्ण समाधान बनाने के लिए एक साथ रख सकते हैं।
यहां वह मेथड है जो सभी डायगोनल्स को एक साथ खींचता है और बोर्ड पर हर क्वीन्स के खिलाफ जांच करता है:
def queen_in_diagonal(row, column, n) diagonals = right_upper_diagonal_for(row, column, n) + left_upper_diagonal_for(row, column, n) + left_lower_diagonal_for(row, column, n) + right_lower_diagonal_for(row, column, n) diagonals.any? { |r, c| r == row && c == column } || diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } } end
बैकट्रैकिंग कैसे लागू करें
इन गैर-तुच्छ चुनौतियों को हल करने के लिए आपको एक महत्वपूर्ण अंतर्दृष्टि, तकनीक या एल्गोरिदम जानने की आवश्यकता होती है।
N-क्वीन्स के मामले में तकनीक बैकट्रैकिंग है।
बैकट्रैकिंग कुछ पिछली कार्रवाई को पूर्ववत कर रहा है (जैसे बोर्ड पर क्वीन्स रखना) और एक अलग कॉन्फिगरेशन के साथ फिर से प्रयास कर रहा है।
मुझे लगा कि यह सबसे कठिन हिस्सा होगा, लेकिन यह काफी आसान निकला।
इसे समझने के लिए मैंने एक छोटा सिमुलेशन चलाया।
मैंने खुद एक बोर्ड और क्वीन्स का प्रतिनिधित्व करने वाले बॉक्स बनाए:
फिर मैंने बॉक्स को बोर्ड पर घुमाया (सीधे अपने माउस से) एल्गोरिदम का अनुकरण करने के लिए।
यहां कोड है:
while row >= n row = @queens_in_board[-1][0] + 1 column = @queens_in_board[-1][1] puts "Backtracking, deleted: #{@queens_in_board.pop}" end
जब आप फंस जाएं तो आप इसे अन्य समस्याओं के लिए भी कर सकते हैं, इसे किसी ड्राइंग प्रोग्राम पर या कागज पर भी बनाएं और इसके साथ खेलें।
यह कैसे काम करता है इसका सार:
- हम ऊपर जाते रहते हैं, यदि हम बोर्ड के शीर्ष पर पहुंच जाते हैं तो इसका मतलब है कि हम इस कॉलम पर क्वीन्स फिट नहीं कर सके
- हम वर्तमान पोजीशन को अंतिम क्वीन्स पर सेट करके और इसे बोर्ड से हटाकर बैकट्रैक करते हैं
- यदि हम इस पोजीशन से क्वीन्स नहीं रख सकते तो हम फिर से बैकट्रैक करते हैं
पंक्ति पोजीशन पर + 1 है हम अंतिम क्वीन्स को पुनः स्थापित करने के लिए कैसे आगे बढ़ते हैं और नए बोर्ड कॉन्फिगरेशन खोलते हैं।
n = 4 के लिए इस कोड को चलाने पर (n = 2 और n = 3 के लिए कोई समाधान नहीं हैं):
"placing at 0 0" "placing at 2 1" Backtracking, deleted: [2, 1] "placing at 3 1" "placing at 1 2" Backtracking, deleted: [1, 2] Backtracking, deleted: [3, 1] Backtracking, deleted: [0, 0] "placing at 1 0" "placing at 3 1" "placing at 0 2" "placing at 2 3"
यह GIF एल्गोरिदम का एक दृश्य उदाहरण है:
पूर्ण कोड
def solve_n_queens(n) @queens_in_board = [] row = 0 column = 0 until @queens_in_board.size == n if queen_in_row(row) || queen_in_diagonal(row, column, n) row += 1 while row >= n row = @queens_in_board[-1][0] + 1 column = @queens_in_board[-1][1] puts "Backtracking, deleted: #{@queens_in_board.pop}" end else place_queen(row, column) p "placing at #{row} #{column}" row = 0 column += 1 end end @queens_in_board end def queen_in_row(row) @queens_in_board.find { |r, c| r == row } end def queen_in_diagonal(row, column, n) diagonals = right_upper_diagonal_for(row, column, n) + left_upper_diagonal_for(row, column, n) + left_lower_diagonal_for(row, column, n) + right_lower_diagonal_for(row, column, n) diagonals.any? { |r, c| r == row && c == column } || diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } } end def top_row?(row, n) row == n end def place_queen(row, column) @queens_in_board << [row, column] end def right_upper_diagonal_for(row, column, n) diagonals = [] until row == n || column == n diagonals << [row += 1, column += 1] end diagonals end def left_upper_diagonal_for(row, column, n) diagonals = [] until row == n || column == 0 diagonals << [row += 1, column -= 1] end diagonals end def right_lower_diagonal_for(row, column, n) diagonals = [] until row == 0 || column == n diagonals << [row -= 1, column += 1] end diagonals end def left_lower_diagonal_for(row, column, n) diagonals = [] until row == 0 || column == 0 diagonals << [row -= 1, column -= 1] end diagonals end def print_board(n) board = Array.new(n) { Array.new(n) { "." } } @queens_in_board.each { |queen| board[queen[0]][queen[1]] = "Q" } board.map { |n| n.join("|") }.reverse end p solve_n_queens(4) p solve_n_queens(5) puts print_board(5)
रिकर्सिव संस्करण
यह एक वैकल्पिक संस्करण है जो सभी संभावित समाधान ढूंढता है।
def solve_n_queens(n, column = 0, queens_in_board = []) @queens_in_board = queens_in_board n.times do |row| unless queen_in_row(row) || queen_in_diagonal(row, column, n) place_queen(row, column) solve_n_queens(n, column + 1, @queens_in_board) remove_last_queen end end puts print_board(n) if @queens_in_board.size == n end
केवल एक चीज जो बदलती है वह है solve_n_queens मेथड।
यह संस्करण सभी आंशिक समाधानों का पता लगाने के लिए रिकर्सन (एक मेथड जो खुद को कॉल करता है) का उपयोग करता है।
जब एक पूर्ण समाधान मिल जाता है तो हम print_board मेथड का उपयोग करके इसे प्रिंट करते हैं।
सारांश
आपने N-क्वीन्स कोडिंग चुनौती और इसे Ruby में कैसे हल करें के बारे में सीखा। आपने अपनी समस्या-समाधान कौशल को बेहतर बनाने का तरीका भी सीखा।
यदि आपको यह लेख पसंद आया तो कृपया इसे किसी ऐसे व्यक्ति के साथ साझा करें जिसे इससे लाभ हो सकता है।
पढ़ने के लिए धन्यवाद!
