पायथन में शतरंज के टुकड़े के लिए हर पोजीशन तक पहुंचने के लिए न्यूनतम चालें खोजने का प्रोग्राम

मान लीजिए, हमारे पास एक शतरंज बोर्ड और एक विशेष नाइट पीस K है, जो बोर्ड के भीतर L आकार में चलता है। यदि पीस (x1, y1) स्थिति में है और यह (x2, y2) पर चलता है तो गति को इस प्रकार वर्णित किया जा सकता है: x2 = x1 ± a; y2 = y1 ± b या x2 = x1 ± b; y2 = y1 ± a; जहां a और b पूर्णांक हैं। हमें उस शतरंज के टुकड़े के लिए न्यूनतम चालों की संख्या पता करनी है जो शतरंज बोर्ड पर स्थिति (0, 0) से स्थिति (n-1, n-1) तक पहुंचने के लिए आवश्यक है। यदि कोई स्थिति पहुंच योग्य नहीं है, तो इसे -1 से चिह्नित किया जाता है, अन्यथा चालों की संख्या लौटाई जाती है। हम n-1 आउटपुट लाइनें प्रिंट करेंगे, जहां प्रत्येक लाइन i में n-1 पूर्णांक होंगे जो प्रत्येक j के लिए पीस द्वारा की जाने वाली न्यूनतम चालों का वर्णन करेंगे।

हल करने के चरण

path_search() फंक्शन परिभाषित करें जो i, j, n लेता है।
- temp_list := (-1, -1) जोड़े से आरंभ एक नया मैप
- queue_positional := (0, 0) जोड़े से आरंभ एक नई लिस्ट
- ver := 8 संभावित नाइट चालें
- जब तक queue_positional खाली न हो, BFS का उपयोग करके खोजें
- लक्ष्य (n-1, n-1) पहुंचने पर पथ की लंबाई गिनें और लौटाएं
मुख्य फंक्शन से: बोर्ड आरंभ करें, सभी (i, j) जोड़े के लिए path_search कॉल करें, समरूपता का उपयोग करके गणना अनुकूलित करें, और परिणाम प्रिंट करें।

सोर्स कोड (पायथन)

from collections import defaultdict

def path_search(i, j, n):
    temp_list = defaultdict(lambda: (-1,-1))
    queue_positional = [(0, 0)]
    ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
    while len(queue_positional) > 0:
        current_element = queue_positional.pop(0)
        for element in ver:
            x = element[0] + current_element[0]
            y = element[1] + current_element[1]
            if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1):
                temp_list[x, y] = current_element
                queue_positional.append((x, y))
                if x == n - 1 and y == n - 1:
                    count_var = 1
                    while temp_list[x,y] != (0,0):
                        count_var += 1
                        x, y = temp_list[x,y]
                    return count_var
    return -1

def solve(n):
    board = defaultdict(lambda: -1)
    for i in range(1, n):
        for j in range(1, i):
            if board[i, j] == -1:
                board[i, j] = path_search(i, j, n)
                board[j, i] = board[i, j]
        if (n - 1) % i == 0:
            board[i, i] = (n - 1) / i
    for i in range(1, n):
        for j in range(1, n - 1):
            print(int(board[i, j]), end=' ')
        print(int(board[i, n - 1]))

solve(6)

इनपुट

आउटपुट

5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1