পাইথনে ৮-পাজল সমাধানের জন্য প্রয়োজনীয় ধাপের সংখ্যা খুঁজে বের করার প্রোগ্রাম

मान लीजिए हमारे पास एक 3x3 बोर्ड है जहां सभी संख्याएं 0 से 8 की रेंज में हैं और कोई संख्या दोहराई नहीं गई है। अब, हम 0 को उसके 4 पड़ोसियों में से किसी एक के साथ स्वैप कर सकते हैं, और हम इसे हल करने की कोशिश कर रहे हैं ताकि सभी व्यवस्थित क्रम में आ जाएं, हमें लक्ष्य तक पहुंचने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढनी है।

तो, अगर इनपुट इस तरह है:

तो आउटपुट 4 होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• एक फंक्शन find_next() परिभाषित करें। यह node लेगा
• moves := एक मैप जो प्रत्येक मान के लिए चालों को सूची के रूप में परिभाषित करता है {0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0, 4, 6], 4: [1, 3, 5, 7], 5: [2, 4, 8], 6: [3, 7], 7: [4, 6, 8], 8: [5, 7]}
• results := एक नई सूची
• pos_0 := node का पहला मान
• प्रत्येक move के लिए moves[pos_0] में, करें
  • new_node := node से एक नई सूची
  • new_node[move] और new_node[pos_0] को स्वैप करें
  • new_node से एक नया टुपल results के अंत में डालें
• results लौटाएं
• एक फंक्शन get_paths() परिभाषित करें। यह dict लेगा
• cnt := 0
• निम्नलिखित को अनंत रूप से करें, करें
  • current_nodes := एक सूची जहां मान cnt के समान है
  • अगर current_nodes का आकार 0 के समान है, तो
    • -1 लौटाएं
  • प्रत्येक node के लिए current_nodes में, करें
    • next_moves := find_next(node)
    • प्रत्येक move के लिए next_moves में, करें
      • अगर move dict में मौजूद नहीं है, तो
        • dict[move] := cnt + 1
      • अगर move (0,1,2,3,4,5,6,7,8) के समान है, तो
        • cnt + 1 लौटाएं
      • cnt := cnt + 1
• मुख्य विधि से निम्नलिखित करें:
• dict := एक नया मैप, flatten := एक नई सूची
• i को 0 से बोर्ड की पंक्ति संख्या तक के लिए, करें
  • flatten := flatten + board[i]
• flatten := flatten की एक कॉपी
• dict[flatten] := 0
• अगर flatten (0,1,2,3,4,5,6,7,8) के समान है, तो
  • 0 लौटाएं
• get_paths(dict) लौटाएं

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

class Solution:
    def solve(self, board):
        dict = {}
        flatten = []
        for i in range(len(board)):
            flatten += board[i]
        flatten = tuple(flatten)
        dict[flatten] = 0
        if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
            return 0
        return self.get_paths(dict)

    def get_paths(self, dict):
        cnt = 0
        while True:
            current_nodes = [x for x in dict if dict[x] == cnt]
            if len(current_nodes) == 0:
                return -1
            for node in current_nodes:
                next_moves = self.find_next(node)
                for move in next_moves:
                    if move not in dict:
                        dict[move] = cnt + 1
                    if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
                        return cnt + 1
            cnt += 1

    def find_next(self, node):
        moves = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4, 6],
            4: [1, 3, 5, 7],
            5: [2, 4, 8],
            6: [3, 7],
            7: [4, 6, 8],
            8: [5, 7],
        }
        results = []
        pos_0 = node.index(0)
        for move in moves[pos_0]:
            new_node = list(node)
            new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
            results.append(tuple(new_node))
        return results

ob = Solution()
matrix = [
    [3, 1, 2],
    [4, 7, 5],
    [6, 8, 0]
]
print(ob.solve(matrix))

ইনপুট

matrix = [
    [3, 1, 2],
    [4, 7, 5],
    [6, 8, 0]
]

আউটপুট

4